1. J.O. Achugbue, F.Y. Chin, Scheduling the open shop to minimize mean flow time. SIAM J. Comput.11, 709–720 (1982)

   Google Scholar 

2. I. Adiri, N. Amit, Openshop and flowshop scheduling to minimize sum of completion times. Comput. Oper. Res.11, 275–284 (1984)

   Google Scholar 

3. M.M. Ahmadian, M. Khatami, A. Salehipour, T.C.E. Cheng, Four decades of research on the open-shop scheduling problem to minimize makespan. Eur. J. Oper. Res. (2021).https://doi.org/10.1016/j.ejor.2021.03.026

4. A.S. Asratian, C.J. Casselgren, On interval edge colorings of (α,β)-biregular bipartite graphs. Discrete Math.307, 1951–1956 (2007)

   Google Scholar 

5. A. Atay, P. Calleja, S. Soteras, Open shop scheduling games. Eur. J. Oper. Res. (2021).https://doi.org/10.1016/j.ejor.2021.02.030

6. W. Banaszczyk, The Steinitz constant of the plane. J. Reine Angew. Math.373, 218–220 (1987)

   Google Scholar 

7. P. Baptiste, On minimizing the weighted number of late jobs in unit execution time open shops. Eur. J. Oper. Res.149, 344–354 (2003)

   Google Scholar 

8. P. Baptiste, P. Brucker, M. Chrobak, C. Dürr, S. A. Kravchenko, F. Sourd, The complexity of mean flow time scheduling problems with release times. J. Sched.10, 139–146 (2007)

   Google Scholar 

9. I. Bárány, T. Fiala, Nearly optimum solution of multimachine scheduling problems (in Hungarian). Szigma15, 177–191 (1982)

   Google Scholar 

10. 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)

    Google Scholar 

11. J.A. Bondy, U.S.R. Murty,Graph Theory with Applications (North-Holland Publishing, Amsterdam, 1976)

    Google Scholar 

12. H. Bräsel, M. Harborth, T. Tautenhahn, P. Willenius, On the set of solutions of the open shop problem. Ann. Oper. Res.92, 241–263 (1999)

    Google Scholar 

13. R.A. Brualdi, Notes on the Birkhoff algorithm for doubly stochastic matrices. Can. Math. Bull.25, 127–147 (1982)

    Google Scholar 

14. P. Brucker,Scheduling Algorithms (Springer, Berlin, 1995)

    Google Scholar 

15. P. Brucker, T. Hilbig, J. Hurink, A branch and bound algorithm for a single-machine scheduling problem with positive and negative time lags. Discrete Appl. Math.94, 77–99 (1999)

    Google Scholar 

16. P. Brucker, J. Hurink, B. Jurisch, Wöstmann, A branch and bound algorithm for the open shop problem. Discrete Appl. Math.76, 43–49 (1997)

    Google Scholar 

17. P. Brucker, B. Jurisch, M. Jurisch, Open-shop problems with unit processing times. Z. Opns. Res.37, 59–73 (1993)

    Google Scholar 

18. P. Brucker, B. Jurisch, T. Tautenhahn, F. Werner, Scheduling unit time open shops to minimize the weighted number of late jobs. Oper. Res. Lett.14, 245 –250 (1993)

    Google Scholar 

19. J. Carlier, É. Pinson, An algorithm for solving the job-shop problem. Manag. Sci.35, 164–176 (1989)

    Google Scholar 

20. B. Chen, V.A. Strusevich, Approximation algorithms for three machine open shop scheduling. ORSA J. Comput.5, 321–328 (1993)

    Google Scholar 

21. B. Chen, W. Yu, How good is a dense shop schedule. Acta Math. Appl. Sin.17, 121–128 (2001)

    Google Scholar 

22. R. Chen,Open Shop Scheduling Problems and Their Dense Schedules. PhD Thesis, East China University of Science and Technology, 2003

    Google Scholar 

23. R. Chen, W. Huang, Z. Men, G. Tang, Open-shop dense schedules: properties and worst-case performance ratio. J. Sched.15, 3–11 (2012)

    Google Scholar 

24. R. Chen, W. Yu, Upper-bound of performance ratio of dense schedules for open-shop (in Chinese). J. East China Univ. Sci. Technol.26, 522–526 (2000)

    Google Scholar 

25. R. Chen, W. Yu, Analysis of operation chain’s properties of dense schedules for open-shop. J. East China Univ. Sci. Technol.29, 522–526 (2003)

    Google Scholar 

26. Y. Cho, S. Sahni, Preemptive scheduling of independent jobs with release and due times on open, flow and job shop. Opns. Res.29, 511–522 (1981)

    Google Scholar 

27. E.G. Coffman Jr., D. Dereniowski, W. Kubiak, An efficient algorithm for finding ideal schedules. Acta Inform.49, 1–14 (2012)

    Google Scholar 

28. E. Cole, K. Ost, S. Schirra, Edge-coloring Bipartite Multigraphs in\(O(E \log D)\). Combinatorica21, 5–12 (2001)

    Google Scholar 

29. U. Dorndorf, E. Pesch, T. Phan-Huy, Solving the open shop scheduling problem. J. Sched.4, 157–174 (2001)

    Google Scholar 

30. J. Du, J.Y.-T. Leung, Minimizing mean flow time in two-machine open shops and flow shops. J. Algorithms14, 24–44 (1993)

    Google Scholar 

31. F. Dufossé, B. Uçar, Notes on Birkhoff-von Neumann decomposition of doubly stochastic matrices. Linear Algebra Appl.479, 108–115 (2016)

    Google Scholar 

32. T. Fiala, An algorithm for the open-shop problem. Math. Oper. Res.8, 100–109 (1983)

    Google Scholar 

33. M.R. Garey, D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, 1979)

    Google Scholar 

34. A.A. Gladky, A two-machine preemptive openshop scheduling problem: an elementary proof of np-completeness. Eur. J. Oper. Res.103, 113–116 (1997)

    Google Scholar 

35. T. Gonzalez, A note on open shop preemptive schedules. IEEE Trans. Comput.C-28, 782–786 (1979)

    Google Scholar 

36. T. Gonzalez, Unit execution time shop problems. Math. Oper. Res.7, 57–66 (1982)

    Google Scholar 

37. T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time. J. ACM23, 665–679 (1976)

    Google Scholar 

38. J. Grabowski, E. Nowicki, S. Zdrzałka, A block approach for single-machine scheduling with release dates and due dates. Eur. J. Oper. Res.26, 278 –285 (1986)

    Google Scholar 

39. 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)

    Google Scholar 

40. A. Grigoriev,High Multiplicity Scheduling Problems. PhD Thesis, Maastricht University, 2003

    Google Scholar 

41. D. Grimes, E. Hebrard, A. Malapert, Closing the open shop: Contradicting conventional wisdom, inInternational Conference on Principles and Practice of Constraint Programming (Springer, 2009), pp. 400–408

    Google Scholar 

42. C. Guéret, N. Jussien, C. Prins, Using intelligent backtracking to improve branch-and-bound methods: an application to open-shop problems. Eur. J. Oper. Res.127, 344– 354 (2000)

    Google Scholar 

43. C. Guéret, C. Prins, A new lower bound for the open-shop problem. Ann. Oper. Res.92, 165–183 (1999)

    Google Scholar 

44. G. Hardy, J. Littlewood, G. Polya,Inequalities (Cambridge University Press, Cambridge, 1952)

    Google Scholar 

45. H. Hoogeveen, P. Schuurman, G.J. Woeginger, Nonapproximability results for scheduling problems with minsum criteria. INFORMS J. Comput.13, 157–168 (2001)

    Google Scholar 

46. W.A. Horn, Some simple scheduling algorithms. Naval Res. Logist. Q.21, 177–185 (1974)

    Google Scholar 

47. J. Józefowska, B. Jurisch, W. Kubiak, Scheduling shops to minimize the weighted number of late jobs. Oper. Res. Lett.16, 277–283 (1994)

    Google Scholar 

48. A. Kononov, S. Sevastyanov, M. Sviridenko, A complete 4-parametric complexity classification of short shop scheduling problems. J. Sched.15, 427–446 (2012)

    Google Scholar 

49. C. Koulamas, G.J. Kyparisis, Open shop scheduling to minimize the number of late jobs. Naval Res. Logist.45, 525–532 (1998)

    Google Scholar 

50. S.A. Kravchenko, On the complexity of minimizing the number of late jobs in unit time open shop. Discrete Appl. Math.100, 127–132 (2000)

    Google Scholar 

51. M. Kubale, Open shop problem with zero-one time operations and integer date/deadline intervals. Discrete Appl. Math.76, 213–223 (1997)

    Google Scholar 

52. W. Kubiak, A pseudo-polynomial algorithm for a two-machine no-wait job-shop scheduling problem. Eur. J. Oper. Res.43, 267–270 (1989)

    Google Scholar 

53. W. Kubiak, C. Sriskandarajah, K. Zaras, A note on the complexity of open shop scheduling problems. INFOR29 (1991)

    Google Scholar 

54. G.J. Kyparisis, C. Koulamas, Open shop scheduling with makespan and total completion time criteria. Comput. Oper. Res.27, 15–27 (2000)

    Google Scholar 

55. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Minimizing maximum lateness in a two-machine open shop. Math. Oper. Res.6, 153–158 (1981)

    Google Scholar 

56. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, Minimizing maximum lateness in a two-machine open shop (erratum). Math. Oper. Res.7, 635 (1982)

    Google Scholar 

57. J.K. Lenstra, Unpublished.

    Google Scholar 

58. C-F. Liaw, Scheduling two-machine preemptive open shops to minimize total completion times. Comput. Oper. Res.31, 1349–1363 (2004)

    Google Scholar 

59. C.Y. Liu, R.L. Bulfin, On the complexity of preemptive open-shop scheduling problems. Oper. Res. Lett.4, 71–74 (1985)

    Google Scholar 

60. C.Y. Liu, R.L. Bulfin, Scheduling open shops with unit execution times to minimize functions of due dates. Oper. Res.36, 553–559 (1988)

    Google Scholar 

61. L. Lu, M.E. Posner, An NP-hard open shop scheduling problem with polynomial average time complexity. Math. Oper. Res.18, 12–38 (1993)

    Google Scholar 

62. I.N. Lushchakova, S.A. Kravchenko, Two-machine shop scheduling with zero and unit processing times. Eur. J. Oper. Res.107, 378–388 (1998)

    Google Scholar 

63. A. Malapert, H. Cambazard, C. Guéret, N. Jussien, A. Langevin, L.M. Rousseau, An optimal constraint programming approach to the open-shop problem. INFORMS J. Comput.24, 228–244 (2012)

    Google Scholar 

64. V.M. Malhotra, M.P. Kumar, S.N. Maheshwari, AnO(|V |³) Algorithm for finding maximum flows in networks. Info. Process. Lett.7, 277–278 (1978)

    Google Scholar 

65. T. Masuda, H. Ishii, Two machine open shop scheduling problem with bi-criteria. Discrete Appl. Math.52, 253–259 (1994)

    Google Scholar 

66. R. McNaughton, Scheduling with deadlines and loss functions. Manag. Sci.6, 1–12 (1959)

    Google Scholar 

67. A. Ozolins, Dynamic programming approach for solving the open shop problem. Central Eur. J. Oper. Res.29, 291–306 (2021)

    Google Scholar 

68. M. Queyranne, M. Sviridenko, A (2+𝜖)-approximation algorithm for the generalized preemptive open shop problem with minsum objective. J. Algorithms45, 202–212 (2002)

    Google Scholar 

69. S.V. Sevastianow, A polynomially solvable case of the open shop problem with arbitrary number of machines (In Russian). Kibernetika i Systemnii Analiz6, 135–154 (1992)

    Google Scholar 

70. S.V. Sevastianow, On some geometric methods in scheduling theory: a survey. Discrete Appl. Math.55, 59–82 (1994)

    Google Scholar 

71. S.V. Sevastianow, G.J. Woeginger, Makespan minimization in open shops: a polynomial time approximation scheme. Math. Program.82, 191–198 (1998)

    Google Scholar 

72. S.V. Sevast’janow, Vector summation in Banach Space and polynomial algorithms for flow shops and open shops. Math. Oper. Res20, 90–103 (1995)

    Google Scholar 

73. S.V. Sevast’janow, W. Banaszczyk, To the Steinitz lemma in coordinate form. Discrete Math.169, 145–152 (1997)

    Google Scholar 

74. E.V. Shchepin, N. Vakhania, On the geometry, preemptions and complexity of multiprocessor and shop scheduling. Ann. Oper. Res.159, 183–213 (2008)

    Google Scholar 

75. E.V. Shchepin, N. Vakhania, A note on the proof of the complexity of the little preemptive open-shop problem. Ann. Oper. Res.191, 251–253 (2011)

    Google Scholar 

76. E. Taillard, Benchmarks for basic scheduling problems. Eur. J. Oper. Res.64, 278–285 (1993)

    Google Scholar 

77. N. Tamura, A. Taga, S. Kitagawa, M. Banbara, Compiling finite linear CSP into SAT. Constraints14, 254–272 (2009)

    Google Scholar 

78. É. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res.34, 250–256 (1986)

    Google Scholar 

79. V.G. Timkovsky, Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. Eur. J. Oper. Res.149, 355–376 (2003)

    Google Scholar 

80. G. Vairaktarakis, S. Sahni, Dual criteria preemptive open shop problems with minimum finish time. Naval Res. Logist.42, 103–121 (1995)

    Google Scholar 

81. D.P. Williamson, L.A. Hall, H. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevast’janow, D.B. Shmoys, Short shop schedules. Oper. Res.45, 288–294 (1997)

    Google Scholar 

82. 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

    Google Scholar 

Download references