Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence

This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O( n2) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An O( n5) algorithm is developed to find an optimal batching decision. © 2011 Elsevier B.V. All rights reserved