New Heuristics for the Flow Line Problem with Setup Costs

Abstract: In this work we present two heuristics for the flowshop machine scheduling problem with setup costs and makespan minimization criteria. One of the proposed procedures is an extension of an algorithm that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has successfully addressed many kinds of combinatorial optimization problems. Both procedures are compared to a previously developed algorithm. In addition, a postprocessing phase for improving the quality of the solutions is developed and adapted to each of the heuristics. All procedures are compared for two different classes of randomly generated instances. It is observed that for the case where both processing times and setup times are identically distributed, the existing heuristic proves superior to the proposed approaches; for the case where setup times are an order of magnitude smaller than the processing times, the proposed procedures outperform the existing heuristic.