Permutation schedules for a two-machine flow shop with storage
- Publication Type:
- Journal Article
- Operations Research Letters, 2016, 44 (2), pp. 153 - 157
- Issue Date:
© 2015 Elsevier B.V. All rights reserved. This paper considers a two-machine flow shop problem with a buffer, arising in various applications, and addresses a fundamental question of the existence of an optimal permutation schedule. The paper proves that the problem of recognising whether an instance has an optimal permutation schedule is NP-complete in the strong sense, and estimates the deviation from the optimal makespan as a result of the restriction to permutation schedules only.
Please use this identifier to cite or link to this item: