Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem
- 20 June 2016
- journal article
- research article
- Published by Wiley in International Transactions in Operational Research
- Vol. 26 (2) , 707-724
Abstract
This work addresses the unrelated parallel machine scheduling problem with sequence‐dependent setup times, in which a set of jobs must be scheduled for execution by one of the several available machines. Each job has a machine‐dependent processing time. Furthermore, given multiple jobs, there are additional setup times, which vary based on the sequence and machine employed. The objective is to minimize the schedule's completion time (makespan). The problem is NP‐hard and of significant practical relevance. The present paper investigates the performance of four different stochastic local search (SLS) methods designed for solving the particular scheduling problem: simulated annealing, iterated local search, late acceptance hill‐climbing, and step counting hill‐climbing. The analysis focuses on design questions, tuning effort, and optimization performance. Simple neighborhood structures are considered. All proposed SLS methods performed significantly better than two state‐of‐the‐art hybrid heuristics, especially for larger instances. Updated best‐known solutions were generated for 901 of the 1000 large benchmark instances considered, demonstrating that particular SLS methods are simple yet powerful alternatives to current approaches for addressing the problem. Implementations of the contributed algorithms have been made available to the research community.Keywords
Funding Information
- Fundação de Amparo à Pesquisa do Estado de Minas Gerais
- Conselho Nacional de Desenvolvimento Científico e Tecnológico
- Federaal Wetenschapsbeleid
- Hercules Foundation
This publication has 19 references indexed in Scilit:
- A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup timesEuropean Journal of Operational Research, 2011
- A survey of scheduling problems with setup times or costsEuropean Journal of Operational Research, 2008
- Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighbourhood searchIMA Journal of Management Mathematics, 2007
- 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
- Variable neighborhood searchComputers & Operations Research, 1997
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealingJournal of Computational Physics, 1990
- Optimization by Simulated AnnealingScience, 1983
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979