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

Publication Type:
Journal Article
Citation:
Discrete Optimization, 2012, 9 (1), pp. 29 - 39
Issue Date:
2012-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012001330OK.pdf514.55 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: