Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141477 | Discrete Optimization | 2012 | 11 Pages |
This paper addresses scheduling nn 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)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)O(n5) algorithm is developed to find an optimal batching decision.