Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines - Université de Lorraine Access content directly
Journal Articles Annals of Operations Research Year : 2020

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

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 ∈ 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
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

Cite

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⟩
9 View
25 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More