Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence
- Publication Type:
- Journal Article
- Discrete Optimization, 2012, 9 (1), pp. 29 - 39
- Issue Date:
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.
Please use this identifier to cite or link to this item: