An Enhanced TSP-Based Heuristic for Makespan Minimization in a Flow Shop with Setup Times |
| |
Authors: | Roger Z Ríos-Mercado Jonathan F Bard |
| |
Institution: | (1) Department of Industrial Engineering, Texas A&M University, College Station, Texas, 77843–3131;(2) Graduate Program in Operations Research, University of Texas, Austin, Texas, 78712–1063 |
| |
Abstract: | This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best. |
| |
Keywords: | flow shop scheduling sequence-dependent setup times heuristics traveling salesman problem |
本文献已被 SpringerLink 等数据库收录! |
|