Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times

Abstract

This paper addresses the problem of minimizing total completion time in a two-machine no-wait flowshop where setup times of the jobs are sequence-dependent. Optimal solutions are obtained for two special flowshops and a dominance relation is developed for the general problem. Several heuristic algorithms with the computational complexity of O(n²) and O(n³) are constructed. The heuristics consist of two phases: in the first phase a starting list is developed and in the second a repeated insertion technique is applied. Computational experience demonstrates that the concept of repeated insertion application is quite useful for any starting list and that solutions for all starting lists converge to about the same value of less than 1% after a few iterations.

Keywords:

• two-machine flowshop
• setup time
• no-wait
• completion time
• heuristics