1994-10-01
On non-permutation solutions to some two machine flow shop scheduling problems
Publication
Publication
Mathematical Methods of Operations Research , Volume 39 - Issue 3 p. 305- 319
In this paper, we study two versions of the two machine flow shop scheduling problem, where schedule length is to be minimized. First, we consider the two machine flow shop with setup, processing, and removal times separated. It is shown that an optimal solution need not be a permutation schedule, and that the problem is NP-hard in the strong sense, which contradicts some known results. The tight worst-case bound for an optimal permutation solution in proportion to a global optimal solution is shown to be 3/2. An O(n) approximation algorithm with this bound is presented. Secondly, we consider the two machine flow shop with finite storage capacity. Again, it is shown that there may not exist an optimal solution that is a permutation schedule, and that the problem is NP-hard in the strong sense.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/BF01435460, hdl.handle.net/1765/70366 | |
| Mathematical Methods of Operations Research | |
| Organisation | Rotterdam School of Management (RSM), Erasmus University |
|
Strusevich, V., & Zwaneveld, P. (1994). On non-permutation solutions to some two machine flow shop scheduling problems. Mathematical Methods of Operations Research, 39(3), 305–319. doi:10.1007/BF01435460 |
|
