A scatter search approach to sequence-dependent setup times job shop scheduling |
| |
Authors: | Andrew Manikas Yih-Long Chang |
| |
Affiliation: | 1. University of Wisconsin-Oshkosh , Oshkosh, WI, USA andrew.manikas@mgt.gatech.edu;3. The College of Management, Georgia Institute of Technology , Atlanta, GA, USA |
| |
Abstract: | Scheduling jobs on multiple machines is a difficult problem when real-world constraints such as the sequence setup time, setup times for jobs and multiple criteria are used for solution goodness. It is usually sufficient to obtain a near-optimal solution quickly when an optimal solution would require days or weeks of computation. Common scheduling heuristics such as Shortest Processing Time can be used to obtain a feasible schedule quickly, but are not designed for multiple simultaneous objectives. We use a new meta-heuristic known as a scatter search (SS) to solve these types of job shop scheduling problems. The results are compared with solutions obtained by common heuristics, a tabu search, simulated annealing, and a genetic algorithm. We show that by combining the mechanism of diversification and intensification, SS produces excellent results in a very reasonable computation time. The study presents an efficient alternative for companies with a complicated scheduling and production situation. |
| |
Keywords: | operations management operations planning operations strategy operational research production management production modelling production planning quality management scheduling manufacturing systems |
|
|