Permutation vs. non-permutation flow shop schedules. (English) Zbl 0742.90045
Summary: In studying the \(m\)-machine flow shop scheduling problem, it is common practice to focus attention on permutation schedules. We show that for the problem of minimizing the maximum completion time, this assumption can be a costly one, by exhibiting a family of instances for which the value of the best permutation schedule is worse than that of the true optimal schedule by a factor of more than \({1\over 2}\sqrt m\).
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
approximation algorithms; flow shop scheduling; permutation schedules; maximum completion timeReferences:
| [1] | Erdös, P.; Szekeres, A., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · Zbl 0012.27010 |
| [2] | Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., Sequencing and scheduling: algorithms and complexity, (Technical Report BS-R8909 (1989), Centre for Mathematics and Computer Science: Centre for Mathematics and Computer Science Amsterdam) · Zbl 0482.68035 |
| [3] | Röck, H.; Schmidt, G., Machine aggregation heuristics in shop scheduling, (Technical Report Bericht 82-11, Fachbereich 20 Mathematik (1982), Technische Universität Berlin) · Zbl 0521.90061 |
| [4] | Röck, H.; Schmidt, G., Machine aggregation heuristics in shop-scheduling, Methods Oper. Res., 45, 303-314 (1983) · Zbl 0521.90061 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
