On non-permutation solutions to some two machine flow shop scheduling problems |
| |
Authors: | Vitaly A. Strusevich Carin M. Zwaneveld |
| |
Affiliation: | (1) Econometric Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands;(2) Tinbergen Institute, Erasmus University Rotterdam, P.O. Box 1738, 3000 DR Rotterdam, The Netherlands |
| |
Abstract: | 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 isNP-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 isNP-hard in the strong sense. |
| |
Keywords: | flow shop permutation schedules complexity approximation |
本文献已被 SpringerLink 等数据库收录! |
|