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:
Filename Description Size
1-s2.0-S0167637715001716-main.pdfPublished Version446.28 kB
Adobe PDF
Full metadata record
© 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: