IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v40y2020i2d10.1007_s10878-020-00591-3.html
   My bibliography  Save this article

Multiprocessor open shop problem: literature review and future directions

Author

Listed:
  • Zeynep Adak

    (Gebze Technical University)

  • Mahmure Övül Arıoğlu Akan

    (Marmara University)

  • Serol Bulkan

    (Marmara University)

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.

Suggested Citation

  • Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 2020. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 547-569, August.
  • Handle: RePEc:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00591-3
    DOI: 10.1007/s10878-020-00591-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00591-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-020-00591-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    2. Chen, Bo & Strusevich, Vitaly A., 1993. "Worst-case analysis of heuristics for open shops with parallel machines," European Journal of Operational Research, Elsevier, vol. 70(3), pages 379-390, November.
    3. D. P. Williamson & L. A. Hall & J. A. Hoogeveen & C. A. J. Hurkens & J. K. Lenstra & S. V. Sevast'janov & D. B. Shmoys, 1997. "Short Shop Schedules," Operations Research, INFORMS, vol. 45(2), pages 288-294, April.
    4. Robert McNaughton, 1959. "Scheduling with Deadlines and Loss Functions," Management Science, INFORMS, vol. 6(1), pages 1-12, October.
    5. Gupta, Yash P. & Evans, Gerald W. & Gupta, Mahesh C., 1991. "A review of multi-criterion approaches to FMS scheduling problems," International Journal of Production Economics, Elsevier, vol. 22(1), pages 13-31, September.
    6. Matta, Marie E. & Elmaghraby, Salah E., 2010. "Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop," European Journal of Operational Research, Elsevier, vol. 201(3), pages 720-728, March.
    7. Tamer Abdelmaguid & Mohamed Shalaby & Mohamed Awwad, 2014. "A tabu search approach for proportionate multiprocessor open shop scheduling," Computational Optimization and Applications, Springer, vol. 58(1), pages 187-203, May.
    8. Jianming Dong & Ruyan Jin & Jueliang Hu & Guohui Lin, 2019. "A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 668-684, February.
    9. Liaw, Ching-Fang, 2000. "A hybrid genetic algorithm for the open shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 124(1), pages 28-42, July.
    10. Jiawei Zhang & Ling Wang & Lining Xing, 2019. "Large-scale medical examination scheduling technology based on intelligent optimization," Journal of Combinatorial Optimization, Springer, vol. 37(1), pages 385-404, January.
    11. Nagar, Amit & Haddock, Jorge & Heragu, Sunderesh, 1995. "Multiple and bicriteria scheduling: A literature survey," European Journal of Operational Research, Elsevier, vol. 81(1), pages 88-104, February.
    12. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    13. Jianming Dong & Joshua Chang & Bing Su & Jueliang Hu & Guohui Lin, 2020. "Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments," Journal of Scheduling, Springer, vol. 23(5), pages 595-608, October.
    14. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zeynep Adak & Mahmure Övül Arıoğlu & Serol Bulkan, 2022. "An ant colony optimization approach for the proportionate multiprocessor open shop," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 785-817, May.
    2. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    3. Deepak Gupta & Sonia Goel & Neeraj Mangla, 2022. "Optimization of production scheduling in two stage Flow Shop Scheduling problem with m equipotential machines at first stage," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 13(3), pages 1162-1169, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Zeynep Adak & Mahmure Övül Arıoğlu Akan & Serol Bulkan, 0. "Multiprocessor open shop problem: literature review and future directions," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    2. Shahaboddin Shamshirband & Mohammad Shojafar & A. Hosseinabadi & Maryam Kardgar & M. Nasir & Rodina Ahmad, 2015. "OSGA: genetic-based open-shop scheduling with consideration of machine maintenance in small and medium enterprises," Annals of Operations Research, Springer, vol. 229(1), pages 743-758, June.
    3. Figueira, J.R. & Liefooghe, A. & Talbi, E.-G. & Wierzbicki, A.P., 2010. "A parallel multiple reference point approach for multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 205(2), pages 390-400, September.
    4. Zeynep Adak & Mahmure Övül Arıoğlu & Serol Bulkan, 2022. "An ant colony optimization approach for the proportionate multiprocessor open shop," Journal of Combinatorial Optimization, Springer, vol. 43(4), pages 785-817, May.
    5. Ahmadian, Mohammad Mahdi & Khatami, Mostafa & Salehipour, Amir & Cheng, T.C.E., 2021. "Four decades of research on the open-shop scheduling problem to minimize the makespan," European Journal of Operational Research, Elsevier, vol. 295(2), pages 399-426.
    6. Yung-Chia Chang & Kuei-Hu Chang & Ching-Ping Zheng, 2022. "Application of a Non-Dominated Sorting Genetic Algorithm to Solve a Bi-Objective Scheduling Problem Regarding Printed Circuit Boards," Mathematics, MDPI, vol. 10(13), pages 1-21, July.
    7. Pempera, Jaroslaw & Smutnicki, Czeslaw, 2018. "Open shop cyclic scheduling," European Journal of Operational Research, Elsevier, vol. 269(2), pages 773-781.
    8. Perez-Gonzalez, Paz & Framinan, Jose M., 2024. "A review and classification on distributed permutation flowshop scheduling problems," European Journal of Operational Research, Elsevier, vol. 312(1), pages 1-21.
    9. Drobouchevitch, Inna G. & Strusevich, Vitaly A., 2001. "Two-stage open shop scheduling with a bottleneck machine," European Journal of Operational Research, Elsevier, vol. 128(1), pages 159-174, January.
    10. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    11. Pagnozzi, Federico & Stützle, Thomas, 2019. "Automatic design of hybrid stochastic local search algorithms for permutation flowshop problems," European Journal of Operational Research, Elsevier, vol. 276(2), pages 409-421.
    12. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    13. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    14. Matthias Bultmann & Sigrid Knust & Stefan Waldherr, 2018. "Flow shop scheduling with flexible processing times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 809-829, July.
    15. Framinan, Jose M. & Leisten, Rainer & Ruiz-Usano, Rafael, 2002. "Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation," European Journal of Operational Research, Elsevier, vol. 141(3), pages 559-569, September.
    16. Arroyo, Jose Elias Claudio & Armentano, Vinicius Amaral, 2005. "Genetic local search for multi-objective flowshop scheduling problems," European Journal of Operational Research, Elsevier, vol. 167(3), pages 717-738, December.
    17. Pan, Quan-Ke & Ruiz, Rubén, 2014. "An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem," Omega, Elsevier, vol. 44(C), pages 41-50.
    18. E. Dhouib & J. Teghem & T. Loukil, 2018. "Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic," Annals of Operations Research, Springer, vol. 267(1), pages 101-134, August.
    19. Lemesre, J. & Dhaenens, C. & Talbi, E.G., 2007. "An exact parallel method for a bi-objective permutation flowshop problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1641-1655, March.
    20. Abdelhamid Boudjelida, 2019. "On the robustness of joint production and maintenance scheduling in presence of uncertainties," Journal of Intelligent Manufacturing, Springer, vol. 30(4), pages 1515-1530, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00591-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.