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

Gais Alhadi (), Imed Kacem (), Pierre Laroche () and Izzeldin M. Osman ()
Additional contact information
Gais Alhadi: Université de Lorraine
Imed Kacem: Université de Lorraine
Pierre Laroche: Université de Lorraine
Izzeldin M. Osman: Sudan University of Science and Technology

Annals of Operations Research, 2020, vol. 285, issue 1, No 17, 369-395

Abstract: 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.

Keywords: Approximation; Maximum lateness; Makespan; Dynamic programming; PTAS; FPTAS (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-019-03250-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:285:y:2020:i:1:d:10.1007_s10479-019-03250-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-019-03250-x

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().