Minimization of maximum lateness on parallel machines with a single server and job release dates

Abdelhak Elidrissi (), Rachid Benmansour, Nicolas Zufferey, Mohammed Benbrahim and David Duvivier
Additional contact information
Abdelhak Elidrissi: International University of Rabat
Rachid Benmansour: National Institute of Statistics and Applied Economics (INSEA)
Nicolas Zufferey: GSEM – University of Geneva
Mohammed Benbrahim: Mohammed V University
David Duvivier: Univ. Polytechnique Hauts-de-France

4OR, 2024, vol. 22, issue 3, No 2, 385 pages

Abstract: Abstract This paper addresses the problem of scheduling independent jobs with release dates on identical parallel machines with a single server. The goal consists in minimizing the maximum lateness. This is a realistic extension of the traditional parallel machine scheduling problem with a single server, in which all jobs are assumed to be available at the beginning of the schedule. This problem, referred to as $$P,S1|r_j|L_{max}$$ P , S 1 | r j | L max , has various applications in practice. To date, research on it has focused on complexity analysis. To solve small-sized instances of the problem, we present two mixed-integer-programming formulations, along with a valid inequality. Due to the $${\mathcal {N}}{\mathcal {P}}$$ N P -hard nature of the problem, we propose a constructive heuristic and two metaheuristics, namely a General Variable Neighborhood Search (GVNS) and a Greedy Randomized Adaptive Search Procedures, both using a Variable Neighborhood Descent as an intensification operator. In the experiments, the proposed algorithms are compared using a set of new instances generated randomly with up to 500 jobs, in line with the related literature. It turns out that GVNS outperforms by far the other approaches.

Keywords: Heuristics; Metaheuristics; Production; Scheduling with a single server; 90B35 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-023-00547-3 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:aqjoor:v:22:y:2024:i:3:d:10.1007_s10288-023-00547-3

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-023-00547-3

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().