Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints
- PDF / 2,109,925 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 188 Views
Heuristic and metaheuristic approaches for parallel machine scheduling under resource constraints Mohamed Amine Abdeljaoued1 · Nour El Houda Saadani1 · Zied Bahroun2 Received: 31 December 2017 / Revised: 4 June 2018 / Accepted: 11 June 2018 © Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract In this paper, an NP-hard parallel machine scheduling problem under resource reservation constraints is studied. The problem is characterized by a set of operations that have to be scheduled on parallel machines, given that the process of each operation requires one specific additional resource, present in a single copy, from a set of reusable resources. The objective is to minimize the makespan. After a mathematical formulation of the problem, two new heuristics that quickly reach a satisfying solution and a simulated annealing metaheuristic aiming to improve the solutions’ quality are provided. The performance of these methods is assessed in a detailed experimental study that includes a comparison with three heuristics from the literature and a worst case analysis of the best performing heuristic. The obtained results show that one of our heuristics outperforms the literature’s methods for nearly all the tested instances, while the simulated annealing algorithm improves the heuristics’ outcomes and ensure near optimal solutions in most of the tests. Keywords Scheduling · Parallel machines · Resource · Heuristic · Metaheuristic
1 Introduction Parallel machine problems are among the most studied subjects in the field of scheduling. Early papers were published in the late 1950s (McNaughton 1959), and work on the subject has continued since. Different kinds of constraints have been studied, * Zied Bahroun [email protected] Mohamed Amine Abdeljaoued [email protected] Nour El Houda Saadani [email protected] 1
F.S.T., LIP2‑LR99ES18, Université de Tunis El Manar, 2092 Tunis, Tunisia
2
Industrial Engineering, ESM Graduate Program, College of Engineering, American University of Sharjah, PO Box 26666, Sharjah, UAE
13
Vol.:(0123456789)
M. A. Abdeljaoued et al.
ranging from the nature of the machines (i.e., identical, uniform) to the jobs’ characteristics (i.e., precedence constraints, preemption). These special features of parallel machine problems have several areas of applications, such as the industrial, commercial, logistics or engineering fields. In this paper, we study a specific resource constrained { parallel machine } scheduling problem: n operations have to be scheduled on a set M1 , M2 … Mm of m identical and parallel machines. For its processing, each operation requires one specific { } additional resource from a set of r reusable resources R1 , R2 … Rr . We assume that all the resources are different and each resource is present in single copy. A machine can process at most one operation at a time and the operations depending on the same resource cannot be performed at the same time. The objective is to minimize the makespan (i.e., the ending date of the last completed op
Data Loading...
