Abstract
We investigate the multiprocessor multi-stage open shop and flow shop scheduling problem. In both problems, there are s stages each consisting of a number m i of parallel identical machines for 1 ≤ i ≤ s. Each job consists of s operations with one operation for each stage. The goal is to find a non-preemptive schedule that minimizes the makespan. We propose polynomial time approximation schemes for the multiprocessor open shop and flow shop scheduling problem when the number of stages s is constant and the numbers of machines m i are non-constant.
This work was done while the first author was associated with the research instutute IDSIA Lugano and supported in part by the Swiss National Science Foundation project 21-55778.98, “Resource Allocation and Scheduling in Flexible Manufacturing Systems”.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Chen, Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage, Journal of the Operational Research Society 46 (1995), 234–244.
B. Chen and V.A. Strusevich, Worst case analysis of heuristics for open shops with parallel machines, European Journal of Operational Research 70 (1993), 379–390.
M.R. Garey and D.S. Johnson, Strong NP-completeness results: Motivation, examples and implications, Journal of the ACM 25 (1978), 499–508.
M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1 (1976), 117–129.
T. Gonzales and S. Sahni, Open shop scheduling to minimize finish time, Journal of the ACM 23 (1976), 665–679.
L.A. Hall, Approximability of flow shop scheduling, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995), 82–91 and Mathematical Programming 82 (1998), 175–190.
D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for scheduling problems: theoretical and practical results, Journal of the ACM 34 (1987), 144–162.
J.A. Hoogeveen, J.K. Lenstra and B. Veltman, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research 89 (1996), 172–175.
K. Jansen, R. Solis-Oba and M.I. Sviridenko, Makespan minimization in job shops: a polynomial time approximation scheme, Proceedings of the 31th Annual ACM Symposium on Theory of Computing, to appear, 1999.
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: Handbook in Operations Research and Management Science, Vol. 4, North-Holland, 1993, 445–522.
P. Schuurman and G.J. Woeginger, Approximation algorithms for the multiprocessor open shop scheduling problem, Operations Research Letters, to appear.
P. Schuurman and G.J. Woeginger, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, Theoretical Computer Science, to appear.
S.V. Sevastianov and G.J. Woeginger, Makespan minimization in open shops: A polynomial time approximation scheme, Mathematical Programming 82 (1998), 191–198.
C. Sriskandarajah and S.P. Sethi, Scheduling algorithms for flexible flow shops: worst and average case performance, European Journal of Operational Research 43 (1989), 143–160.
D.P. Williamson, L.A. Hall, J.A. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevastianov and D.B. Shmoys, Short shop schedules, Operations Research 45 (1997), 288–294.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jansen, K., Sviridenko, M.I. (2000). Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem. In: Reichel, H., Tison, S. (eds) STACS 2000. STACS 2000. Lecture Notes in Computer Science, vol 1770. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46541-3_38
Download citation
DOI: https://doi.org/10.1007/3-540-46541-3_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67141-1
Online ISBN: 978-3-540-46541-6
eBook Packages: Springer Book Archive