A hybrid genetic algorithm for parallel machine scheduling with setup times
Author:
Open Access
- 1 June 2022
- journal article
- research article
- Published by Springer Nature in Journal of Intelligent Manufacturing
- Vol. 33 (7) , 2059-2073
Abstract
This paper addresses the unrelated parallel machine scheduling problem with sequence and machine dependent setup times and machine eligibility constraints. The objective is to minimize the maximum completion time (makespan). Instances of more than 500 jobs and 50 machines are not uncommon in industry. Such large instances become increasingly challenging to provide high-quality solutions within limited amount of computational time, but so far, have not been adequately addressed in recent literature. A hybrid genetic algorithm is developed, which is lean in the sense that is equipped with a minimal number of parameters and operators, and which is enhanced with an effective local search operator, specifically targeted to solve large instances. For evaluation purposes a new set of larger problems is generated, consisting of up to 800 jobs and 60 machines. An extensive comparative study shows that the proposed method performs significantly better compared to other state-of-the-art algorithms, especially for the new larger instances. Also, it is demonstrated that calibration is crucial and in practice it should be targeted at a narrower set of representative instances.Keywords
This publication has 31 references indexed in Scilit:
- A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup timesEuropean Journal of Operational Research, 2011
- Parameter tuning for configuring and analyzing evolutionary algorithmsSwarm and Evolutionary Computation, 2011
- Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup timesApplied Soft Computing, 2011
- A survey of scheduling problems with setup times or costsEuropean Journal of Operational Research, 2008
- Scheduling and lot sizing with sequence-dependent setup: A literature reviewIIE Transactions, 2006
- Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup TimesJournal of Intelligent Manufacturing, 2006
- Unrelated parallel machine scheduling with setup times using simulated annealingRobotics and Computer-Integrated Manufacturing, 2002
- SOLVING THE MULTIPLE-MACHINE WEIGHTED FLOW TIME PROBLEM USING TABU SEARCHIIE Transactions, 1993
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Complexity of Machine Scheduling Problems1977