Article ID: | iaor19992910 |
Country: | Netherlands |
Volume: | 110 |
Issue: | 1 |
Start Page Number: | 76 |
End Page Number: | 98 |
Publication Date: | Oct 1998 |
Journal: | European Journal of Operational Research |
Authors: | Bard Jonathan F., Ros-Mercado Roger Z. |
Keywords: | heuristics, programming: travelling salesman |
This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.