Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines - Université de Lorraine Accéder directement au contenu
Article Dans Une Revue Annals of Operations Research Année : 2020

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

Résumé

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 ∈ J has a processing time p j and a delivery time q j. The machines are available at time 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 pseudopolynomial time. Then, we present a PTAS (Polynomial Time Approximation Scheme) to generate an approximate Pareto Frontier. In this scheme, we use a simplification technique based on the merging of jobs. Furthermore, we present two FPTAS (Fully Polynomial Time Approximation Scheme) 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.
Fichier principal
Vignette du fichier
main.pdf (629.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03795347 , version 1 (04-10-2022)

Identifiants

Citer

Gais Alhadi, Imed Kacem, Pierre Laroche, Izzeldin Osman. Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines. Annals of Operations Research, 2020, 285 (1-2), pp.369-395. ⟨10.1007/s10479-019-03250-x⟩. ⟨hal-03795347⟩
12 Consultations
61 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More