Variable Neighborhood Search for Identical Parallel Machine Scheduling Problem with a Single Server

Abdelhak El Idrissi (1, 2) , Mohammed Benbrahim (1) , Rachid Benmansour (3, 2) , David Duvivier (2)

1 UM5 - Université Mohammed V de Rabat [Agdal]
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
3 SI2M - Laboratoire Systèmes d'information Multimédia et Mobile

In this paper, we study the m identical parallel machines scheduling problem with a single server to minimize the schedule length (makespan). Each job requires a prior set-up which must be performed by a single server. For this strongly NP-hard problem, a variable neighborhood search is proposed. We conduct a comparative analysis with existing algorithms using previously solved instances from the literature. The results indicate that the algorithm presented in this paper is effective and efficient regarding the quality of the solution: the obtained objective function values are very close to lower bounds

Mots clés: Identical parallel machines scheduling; Scheduling with a single server; Variable neighborhood search

Domaines: Informatique [cs]

Abdelhak El Idrissi, Mohammed Benbrahim, Rachid Benmansour, David Duvivier. Variable Neighborhood Search for Identical Parallel Machine Scheduling Problem with a Single Server. Variable Neighborhood Search, 12010, Springer International Publishing, pp.112-125, 2020, Lecture Notes in Computer Science, 978-3-030-44931-5. ⟨10.1007/978-3-030-44932-2_8⟩. ⟨hal-03691376⟩