Heuristics for the flow line problem with setup costs

Heuristics for the flow line problem with setup costs

0.00 Avg rating0 Votes
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: ,
Keywords: heuristics, programming: travelling salesman
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.