IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v285y2020i1d10.1007_s10479-019-03250-x.html
   My bibliography  Save this article

Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines

Author

Listed:
  • Gais Alhadi

    (Université de Lorraine
    University of Gezira)

  • Imed Kacem

    (Université de Lorraine)

  • Pierre Laroche

    (Université de Lorraine)

  • Izzeldin M. Osman

    (Sudan University of Science and Technology)

Abstract

We consider a multiobjective scheduling problem, with the aim of minimizing the maximum lateness and the makespan on two identical machines. In this problem, we are given a set J of n jobs to be scheduled on two identical machines. Each job $$j\in J$$j∈J has a processing time $$p_j$$pj and a delivery time $$q_j$$qj. The machines are available at time $$t=0$$t=0 and each of them can process at most one job at a given time. This paper proposes an exact algorithm (based on a dynamic programming) to generate the complete Pareto Frontier in a pseudo-polynomial time. Then, we present a polynomial time approximation scheme (PTAS) to generate an approximate Pareto Frontier. In this scheme, we use a simplification technique based on the merging of jobs. Furthermore, we present two fully polynomial time approximation scheme (FPTAS) to generate an approximate Pareto Frontier, the first one is based on the conversion of the dynamic programming, the second one is applied to the simplified instances given by the PTAS. The proposed FPTAS algorithms are strongly polynomial. Finally, some numerical experiments are provided in order to compare the four proposed approaches.

Suggested Citation

  • Gais Alhadi & Imed Kacem & Pierre Laroche & Izzeldin M. Osman, 2020. "Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines," Annals of Operations Research, Springer, vol. 285(1), pages 369-395, February.
    • Handle: RePEc:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03250-x
    DOI: 10.1007/s10479-019-03250-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-019-03250-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-019-03250-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Demange, Marc & Paschos, Vangelis Th., 2005. "Polynomial approximation algorithms with performance guarantees: An introduction-by-example," European Journal of Operational Research, Elsevier, vol. 165(3), pages 555-568, September.
    2. Cheng He & Hao Lin & Yixun Lin & Ji Tian, 2013. "Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 21(1), pages 177-186, January.
    3. Sarah Ben Amor & Kazimierz Zaras & Ernesto A. Aguayo, 2017. "The value of additional information in multicriteria decision making choice problems with information imperfections," Annals of Operations Research, Springer, vol. 253(1), pages 61-76, June.
    4. Florios, Kostas & Mavrotas, George, 2014. "Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems," MPRA Paper 105074, University Library of Munich, Germany.
    5. Allahverdi, Ali & Aldowaisan, Tariq, 2004. "No-wait flowshops with bicriteria of makespan and maximum lateness," European Journal of Operational Research, Elsevier, vol. 152(1), pages 132-147, January.
    6. Ben Amor, Sarah & Martel, Jean-Marc, 2014. "A new distance measure including the weak preference relation: Application to the multiple criteria aggregation procedure for mixed evaluations," European Journal of Operational Research, Elsevier, vol. 237(3), pages 1165-1169.
    7. Geng, Zhichao & Yuan, Jinjiang & Yuan, Junling, 2018. "Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost," Applied Mathematics and Computation, Elsevier, vol. 332(C), pages 1-18.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Adel Kacem & Abdelaziz Dammak, 2021. "Multi-objective scheduling on two dedicated processors," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 694-721, October.
    2. Ye Wang & Jiafu Tang, 2022. "Optimized skill configuration for the seru production system under an uncertain demand," Annals of Operations Research, Springer, vol. 316(1), pages 445-465, September.
    3. Anghinolfi, Davide & Paolucci, Massimo & Ronco, Roberto, 2021. "A bi-objective heuristic approach for green identical parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 289(2), pages 416-434.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cheng He & Chunqi Xu & Hao Lin, 2020. "Serial-batching scheduling with two agents to minimize makespan and maximum cost," Journal of Scheduling, Springer, vol. 23(5), pages 609-617, October.
    2. Oracio I. Barbosa-Ayala & Jhon A. Montañez-Barrera & Cesar E. Damian-Ascencio & Adriana Saldaña-Robles & J. Arturo Alfaro-Ayala & Jose Alfredo Padilla-Medina & Sergio Cano-Andrade, 2020. "Solution to the Economic Emission Dispatch Problem Using Numerical Polynomial Homotopy Continuation," Energies, MDPI, vol. 13(17), pages 1-15, August.
    3. David Bergman & Merve Bodur & Carlos Cardonha & Andre A. Cire, 2022. "Network Models for Multiobjective Discrete Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 990-1005, March.
    4. Lakmali Weerasena & Aniekan Ebiefung & Anthony Skjellum, 2022. "Design of a heuristic algorithm for the generalized multi-objective set covering problem," Computational Optimization and Applications, Springer, vol. 82(3), pages 717-751, July.
    5. Abdennour Azerine & Mourad Boudhar & Djamal Rebaine, 2022. "A two-machine no-wait flow shop problem with two competing agents," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 168-199, January.
    6. Wang, Chuyang & Li, Xiaoping & Wang, Qian, 2010. "Accelerated tabu search for no-wait flowshop scheduling problem with maximum lateness criterion," European Journal of Operational Research, Elsevier, vol. 206(1), pages 64-72, October.
    7. Justus Bonz, 2021. "Application of a multi-objective multi traveling salesperson problem with time windows," Public Transport, Springer, vol. 13(1), pages 35-57, March.
    8. Geng, Zhichao & Yuan, Jinjiang & Yuan, Junling, 2018. "Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost," Applied Mathematics and Computation, Elsevier, vol. 332(C), pages 1-18.
    9. Alexandros Nikas & Angelos Fountoulakis & Aikaterini Forouli & Haris Doukas, 2022. "A robust augmented ε-constraint method (AUGMECON-R) for finding exact solutions of multi-objective linear programming problems," Operational Research, Springer, vol. 22(2), pages 1291-1332, April.
    10. Boris Mirkin & Trevor I. Fenner, 2019. "Distance and Consensus for Preference Relations Corresponding to Ordered Partitions," Journal of Classification, Springer;The Classification Society, vol. 36(2), pages 350-367, July.
    11. Ausiello, G. & Paschos, V.Th., 2006. "Reductions, completeness and the hardness of approximability," European Journal of Operational Research, Elsevier, vol. 172(3), pages 719-739, August.
    12. Mohammed Mahrach & Gara Miranda & Coromoto León & Eduardo Segredo, 2020. "Comparison between Single and Multi-Objective Evolutionary Algorithms to Solve the Knapsack Problem and the Travelling Salesman Problem," Mathematics, MDPI, vol. 8(11), pages 1-23, November.
    13. Kalczynski, Pawel Jan & Kamburowski, Jerzy, 2007. "On no-wait and no-idle flow shops with makespan criterion," European Journal of Operational Research, Elsevier, vol. 178(3), pages 677-685, May.
    14. Ömer Faruk Yılmaz & Büşra Yazıcı, 2022. "Tactical level strategies for multi-objective disassembly line balancing problem with multi-manned stations: an optimization model and solution approaches," Annals of Operations Research, Springer, vol. 319(2), pages 1793-1843, December.
    15. Allahverdi, Ali & Aydilek, Harun & Aydilek, Asiye, 2018. "No-wait flowshop scheduling problem with two criteria; total tardiness and makespan," European Journal of Operational Research, Elsevier, vol. 269(2), pages 590-601.
    16. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    17. Qi-Xia Yang & Long-Cheng Liu & Min Huang & Tian-Run Wang, 2024. "Algorithms for a two-machine no-wait flow shop scheduling problem with two competing agents," Journal of Combinatorial Optimization, Springer, vol. 48(1), pages 1-17, August.
    18. Lakmali Weerasena & Margaret M. Wiecek & Banu Soylu, 2017. "An algorithm for approximating the Pareto set of the multiobjective set covering problem," Annals of Operations Research, Springer, vol. 248(1), pages 493-514, January.
    19. Dinçer Konur & Hadi Farhangi & Cihan H. Dagli, 2016. "A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 967-1006, October.
    20. Yijie Li, 2023. "Bicriteria fabrication scheduling of two-component jobs on a single machine," Operational Research, Springer, vol. 23(4), pages 1-13, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03250-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.