Efficient heuristics and metaheuristics for the unrelated parallel machine scheduling problem with release dates and setup times

Abstract

Parallel machine scheduling problems are among the most studied scheduling problems in the literature. We study the unrelated parallel machine scheduling problem with release dates and machine- and sequence-dependent setup times to minimize the makespan. We introduce three heuristics, five local search methods and three metaheuristics for the problem: the Late Acceptance Hill Climbing and two variants of Simulated Annealing. Furthermore, we introduce a three-set 1620-instance benchmark in which the number of jobs and machines, release dates, processing and setup times are generated according to existing procedures. The proposed approaches are analyzed and compared on the proposed benchmark. We compare the proposed heuristics and derive the best heuristic to be used to generate the initial solution of the metaheuristics. Moreover, we show that the different metaheuristics are efficient, each performing best on one of the sets.

Mohamed Elamine Athmani

PhD student in computer science

My research interests include scheduling, planning, constraints programming and artificial intelligence.

Taha Arbaoui

Associate Professor at University of Technology of Troyes

My research interests include Planning and scheduling, Timetabling, MLxOR, Heuristics and metaheuristics.