Part of the book series:International Series in Operations Research & Management Science ((ISOR,volume 325))
469Accesses
Abstract
We begin by introducing notation, terminology, and definitions for traditional open shop scheduling.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 14871
- Price includes VAT (Japan)
- Softcover Book
- JPY 18589
- Price includes VAT (Japan)
- Hardcover Book
- JPY 18589
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
A.S. Asratian, T.M.J. Denley, R. Häggkvist,Bipartite Graphs and Their Applications. Cambridge Tracts in Mathematics (131) (Cambridge University Press, Cambridge, 1998)
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi,Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties (Springer, Berlin, 1999)
W. Banaszczyk, The Steinitz constant of the plane. J. Reine Angew. Math.373, 218–220 (1987)
R.B. Bapat, T.E.S. Raghavan,Nonnegative Matrices and Applications (Cambridge University Press, Cambridge, 1997)
I. Bárány, A vector-sum theorem and its application to improving flow shop guarantees. Math. Oper. Res.6, 445–452 (1981)
I. Bárány, On the power of linera dependencies, inBuilding Bridges Between Math and Computer Science, ed. by M. Grötschel, G.O.H. Katona (Springer, 2008), pp. 31–45
C. Berge,The Theory of Graphs (Dover Publications, New York, 2001)
J. Błażewicz, K. Ecker, E. Pesch, G. Schmidt, J. Wȩglarz,Handbook on Scheduling: From Theory to Applications. International Handbooks on Information Systems (Springer, Berlin, 2007)
J.A. Bondy, U.S.R. Murty,Graph Theory with Applications (North-Holland Publishing, Amsterdam, 1976)
P. Brucker,Scheduling Algorithms (Springer, Berlin, 1995)
E. Cole, K. Ost, S. Schirra, Edge-coloring bipartite multigraphs in\(O(E \log D)\). Combinatorica21, 5–12 (2001)
D. de Werra, On some combinatorial problems arising in scheduling. INFOR8, 165–175 (1970)
J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Nat. Bur. Stand.69(1–2), 125–130 (1965)
H.N. Gabow, O. Kariv, Algorithms for edge coloring bipartite graphs and multigraphs. SIAM J. Comput.11, 117–129 (1982)
M.R. Garey, D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, 1979)
T. Gonzalez, A note on open shop preemptive schedules. IEEE Trans. Comput.C-28, 782–786 (1979)
T. Gonzalez, Open shop scheduling, inHandbook on Scheduling: Algorithms, Models, and Performance Analysis, ed. by J.Y.-T. Leung (Chapman and Hall/CRC, 2004), pp. 6-1–6-14
T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. J. ACM23, 665–679 (1976)
C. Gotlieb, The construction of class-teacher time-tables, inProc. IFIP Congress 62, Munich (North-Holland, Amsterdam, 1963)
R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discr. Math.5, 287–326 (1979)
V.S. Grinberg, S.V. Sevast’janow, Value of the Steinitz constant (in Russian). Funktsional. Anal. i Prilozhen. (Functional Anal. Appl.)14, 125–126 (1980)
R.A. Horn, C.R. Johnson,Matrix Analysis, 2nd edn. (Cambridge University Press, Cambridge, 2013)
D. König, Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Math. Ann.77, 453–465 (1916)
A.W. Marshall, I. Olkin,Inequalities: Theory of Majorization and Its Applications (Academic Press, New York, 1979)
M.L. Pinedo,Scheduling: Theory, Algorithms, and Systems, 5th edn. (Springer, Berlin, 2016)
A. Schrijver,Combinatorial Optimization. Polyhedra and Efficiency, vol. A (Springer, Berlin, 2003)
S.V. Sevast’janow, W. Banaszczyk, To the Steinitz lemma in coordinate form. Discrete Math.169, 145–152 (1997)
E. Steinitz, Bedingt konvergente reihen und convexe systeme. J. Reine Angew. Math.143, 128–175 (1913)
G.J. Woeginger, The open shop scheduling problem, in35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), ed. by R. Niedermeier, B. Vallée. Leibniz International Proceedings in Informatics (Dagstuhl Publishing, 2018), pp. 4:1–4:12
Author information
Authors and Affiliations
Memorial University of Newfoundland, St. John’s, NL, Canada
Wieslaw Kubiak
- Wieslaw Kubiak
Search author on:PubMed Google Scholar
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Kubiak, W. (2022). Preliminaries. In: A Book of Open Shop Scheduling. International Series in Operations Research & Management Science, vol 325. Springer, Cham. https://doi.org/10.1007/978-3-030-91025-9_1
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-91024-2
Online ISBN:978-3-030-91025-9
eBook Packages:Business and ManagementBusiness and Management (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative