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

This paper addresses the problem of minimizing total completion time in a t wo-machine no-wait flowshop where setup times of the jobs are sequence-depe ndent. Optimal solutions are obtained for two special flowshops and a domin ance relation is developed for the general problem. Several heuristic algor ithms with the computational complexity of O(n(2)) and O(n(3)) are construc ted. The heuristics consist of two phases: in the first phase a starting li st is developed and in the second a repeated insertion technique is applied . Computational experience demonstrates that the concept of repeated insert ion application is quite useful for any starting list and that solutions fo r all starting lists converge to about the same value of less than 1% after a few iterations.