Skip to main content
SpringerLink
Log in

Multiprocessor open shop problem: literature review and future directions

  • Published:
Journal of Combinatorial Optimization Aims and scope Submit manuscript

Abstract

Multi-processor open shop (MPOS) is a combination of the classical open shop and parallel shop environments. Although there exist wide application areas of this shop environment in both production and service facilities, the research in the field is still limited. In this paper, we provided a detailed review of the research on MPOS problem. With this survey, we aimed to provide a helpful guide to those who are willing to contribute to this open field of study. We have reviewed the studies in MPOS literature under the following topics: mathematical formulations, polynomial-time optimum solution algorithms for few special cases, approximation algorithms, dispatching rules, heuristics and metaheuristics. We further presented test data used in the literature and investigated the ways researchers evaluated their results. Solution representation and parameter tuning in metaheuristic applications have been also covered in detail. There is considerable room for improvement, especially in terms of near-optimal solution approaches. We closely investigated research topics that need particular attention in future research. We believe the review here will be a good starting point to study MPOS problem, even for those who have no prior knowledge of the field.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  • Abdelmaguid TF (2014) A hybrid PSO-TS approach for proportionate multiprocessor open shop scheduling. In: 2014 IEEE international conference on industrial engineering and engineering management, pp 107–111

  • Abdelmaguid TF (2020) Scatter search with path relinking for multiprocessor open shop scheduling. Comput Ind Eng 141:106292

    Google Scholar 

  • Abdelmaguid TF, Shalaby MA, Awwad MA (2014) A tabu search approach for proportionate multiprocessor open shop scheduling. Comput Optim Appl 58(1):187–203

    MathSciNet  MATH  Google Scholar 

  • Anand E, Panneerselvam R (2015) Literature review of open shop scheduling problems. Intell Inf Manag 7(1):33–52

    Google Scholar 

  • Azadeh A, Farahani MH, Torabzadeh S, Baghersad M (2014) Scheduling prioritized patients in emergency department laboratories. Comput Methods Programs Biomed 117(2):61–70

    Google Scholar 

  • Bai D, Zhang ZH, Zhang Q (2016) Flexible open shop scheduling problem to minimize makespan. Comput Oper Res 67:207–215

    MathSciNet  MATH  Google Scholar 

  • Bárány I, Fiala T (1982) Nearly optimum solution of multimachine scheduling problems. Szigma 15(3):177–191

    MathSciNet  MATH  Google Scholar 

  • Blum C (2005) Beam-ACO–hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput Oper Res 32(6):1565–1591

    MATH  Google Scholar 

  • Blum C, Sampels M (2004) An ant colony optimization algorithm for shop scheduling problems. J Math Model Algorithms 3(3):285–308

    MathSciNet  MATH  Google Scholar 

  • Brucker P, Schlie R (1990) Job-shop scheduling with multi-purpose machines. Computing 45(4):369–375

    MathSciNet  MATH  Google Scholar 

  • Chaudhry IA, Khan AA (2016) A research survey: review of flexible job shop scheduling techniques. Int Trans Oper Res 23(3):551–591

    MathSciNet  MATH  Google Scholar 

  • Chen B, Strusevich VA (1993) Worst-case analysis of heuristics for open shops with parallel machines. Eur J Oper Res 70(3):379–390

    MATH  Google Scholar 

  • Chen Y, Zhang A, Chen G, Dong J (2013) Approximation algorithms for parallel open shop scheduling. Inf Process Lett 113(7):220–224

    MathSciNet  MATH  Google Scholar 

  • Chou FD, Wang HM (2013) A simulated annealing to solve four-stage open shops with parallel machines. Materials Engineering and Automatic Control II, Trans Tech Publications, Applied Mechanics and Materials 330:843–847

    Google Scholar 

  • De Werra D, Kis T, Kubiak W (2008) Preemptive open shop scheduling with multiprocessors: polynomial cases and applications. J Schedul 11(1):75–83

    MathSciNet  MATH  Google Scholar 

  • Dong J, Jin R, Hu J, Lin G (2019) A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops. J Combi Optim 37(2):668–684

    MathSciNet  MATH  Google Scholar 

  • Dong J, Chang J, Su B, Hu J, Lin G (2020) Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments. J Sched. https://doi.org/10.1007/s10951-019-00633-7

    Article  Google Scholar 

  • Fan K, Zhai Y, Li X, Wang M (2018) Review and classification of hybrid shop scheduling. Prod Eng 12(5):597–609

    Google Scholar 

  • Goldansaz SM, Jolai F, Anaraki AHZ (2013) A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop. Appl Math Model 37(23):9603–9616

    MathSciNet  MATH  Google Scholar 

  • Gonzalez TF (2007) Handbook of approximation algorithms and metaheuristics. Chapman and Hall/CRC, London

    MATH  Google Scholar 

  • Gonzalez T, Sahni S (1976) Open shop scheduling to minimize finish time. JACM 23(4):665–679

    MathSciNet  MATH  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK, Kan AR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326

    MathSciNet  MATH  Google Scholar 

  • Gupta YP, Evans GW, Gupta MC (1991) A review of multi-criterion approaches to FMS scheduling problems. Int J Prod Econ 22(1):13–31

    Google Scholar 

  • Hurink J, Jurisch B, Thole M (1994) Tabu search for the job-shop scheduling problem with multi-purpose machines. Oper Res Spektrum 15(4):205–215

    MathSciNet  MATH  Google Scholar 

  • Jansen K, Sviridenko MI (2000) Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. In: Annual symposium on theoretical aspects of computer science. Springer, Berlin, pp 455–465

  • Kacem I, Hammadi S, Borne P (2002) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Syst Man Cybern C (Appl Rev) 32(1):1–13

    MATH  Google Scholar 

  • Kis T, De Werra D, Kubiak W (2010) A projective algorithm for preemptive open shop scheduling with two multiprocessor groups. Oper Res Lett 38(2):129–132

    MathSciNet  MATH  Google Scholar 

  • Kononov A, Sviridenko M (2002) A linear time approximation scheme for makespan minimization in an open shop with release dates. Oper Res Lett 30(4):276–280

    MathSciNet  MATH  Google Scholar 

  • Lawler EL, Luby MG, Vazirani VV (1982) Scheduling open shops with parallel machines. Oper Res Lett 1(4):161–164

    MATH  Google Scholar 

  • Lei D (2008) Multi-objective production scheduling: a survey. Int J Adv Manuf Technol 43(9):926

    Google Scholar 

  • Liaw CF (1999) A tabu search algorithm for the open shop scheduling problem. Comput Oper Res 26(2):109–126

    MathSciNet  MATH  Google Scholar 

  • Liaw CF (2000) A hybrid genetic algorithm for the open shop scheduling problem. Eur J Oper Res 124(1):28–42

    MathSciNet  MATH  Google Scholar 

  • Mao W (1995) Multi-operation multi-machine scheduling. In: International conference on high-performance computing and networking. Springer, Berlin, pp 33–38

  • Matta ME (2009) A genetic algorithm for the proportionate multiprocessor open shop. Comput Oper Res 36(9):2601–2618

    MathSciNet  MATH  Google Scholar 

  • Matta ME, Elmaghraby SE (2010) Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. Eur J Oper Res 201(3):720–728

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  • Mejia G, Cendales O, Mendez-Acuna D, Casallas R (2013) A simulated annealing algorithm for the vehicle routing and scheduling problem. In: 22nd international conference on production research

  • Minella G, Ruiz R, Ciavotta M (2008) A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS J Comput 20(3):451–471

    MathSciNet  MATH  Google Scholar 

  • Naderi B, Ghomi SF, Aminnayeri M, Zandieh M (2011) Scheduling open shops with parallel machines to minimize total completion time. J Comput Appl Math 235(5):1275–1287

    MathSciNet  MATH  Google Scholar 

  • Nagar A, Haddock J, Heragu S (1995) Multiple and bicriteria scheduling: a literature survey. Eur J Oper Res 81(1):88–104

    MATH  Google Scholar 

  • Osman IH, Laporte G (1996) Metaheuristics: a bibliography. Ann Oper Res 63(5):511–623

    MATH  Google Scholar 

  • Parra C, Ventura JA (2013) A particle swarm optimization for scheduling a fixed product open shop. In: IIE annual conference. Proceedings, Institute of Industrial and Systems Engineers (IISE), p 2728

  • Queyranne M, Sviridenko M (2002) Approximation algorithms for shop scheduling problems with minsum objective. J Sched 5(4):287–305

    MathSciNet  MATH  Google Scholar 

  • Roy B, Sussmann B (1964) Les problemes d’ordonnancement avec contraintes disjonctives. Research report, Note D.S. no.9 bis, SEMA, Paris, France

  • Schuurman P, Woeginger GJ (1999) Approximation algorithms for the multiprocessor open shop scheduling problem. Oper Res Lett 24(4):157–163

    MathSciNet  MATH  Google Scholar 

  • Sevastianov SV, Woeginger GJ (2001) Linear time approximation scheme for the multiprocessor open shop problem. Discrete Appl Math 114(1–3):273–288

    MathSciNet  MATH  Google Scholar 

  • Shiang WJ, Lin YH, Rau H (2009) Application of simulation to the scheduling problem for a LED sorting system. In: 2009 international conference on machine learning and cybernetics, vol 5. IEEE, pp 2875–2879

  • Sörensen K (2015) Metaheuristics-the metaphor exposed. Int Trans Oper Res 22(1):3–18

    MathSciNet  MATH  Google Scholar 

  • Sun Y, Zhang C, Gao L, Wang X (2011) Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects. Int J Adv Manuf Technol 55(5):723–739

    Google Scholar 

  • Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64(2):278–285

    MathSciNet  MATH  Google Scholar 

  • Trail CD, Ventura J (2012) A multi-objective fixed product flexible open shop problem. In: IIE annual conference. Proceedings, Institute of Industrial and Systems Engineers (IISE), pp 1–6

  • Wang HM, Chou FD (2012) Scheduling of led chip sorting sequencing model in led manufacturing. In: IIE Asian conference, Singapore

  • Wang YTH, Chou FD (2017) A bi-criterion simulated annealing method to solve four-stage multiprocessor open shops with dynamic job release time. In: 2017 international conference on computing intelligence and information system (CIIS), pp 13–17

  • Wang HM, Chou FD (2015) A particle swarm optimization to minimize makespan for a four-stage multiprocessor open shop with dynamic job release time. World J Eng Technol 3(3):78–83

    Google Scholar 

  • Williamson DP, Hall LA, Hoogeveen JA, Hurkens CA, Lenstra JK, Sevast’janov SVE, Shmoys DB (1997) Short shop schedules. Oper Res 45(2):288–294

    MathSciNet  MATH  Google Scholar 

  • Yenisey MM, Yagmahan B (2014) Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega 45:119–135

    Google Scholar 

  • Zhang J, Wang L, Xing L (2019) Large-scale medical examination scheduling technology based on intelligent optimization. J Comb Optim 37(1):385–404

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Gebze Technical University, 41400, Kocaeli, Turkey

    Zeynep Adak

  2. Department of Industrial Engineering, Marmara University, 34722, Istanbul, Turkey

    Mahmure Övül Arıoğlu Akan & Serol Bulkan

Authors
  1. Zeynep Adak
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mahmure Övül Arıoğlu Akan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Serol Bulkan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zeynep Adak.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Adak, Z., Arıoğlu Akan, M.Ö. & Bulkan, S. Multiprocessor open shop problem: literature review and future directions. J Comb Optim 40, 547–569 (2020). https://doi.org/10.1007/s10878-020-00591-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10878-020-00591-3

Keywords

Search

Navigation