Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1142206 | Operations Research Letters | 2016 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Joey Fung, Yakov Zinder,