IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v77y2018icp143-153.html
   My bibliography  Save this article

The Non-Permutation Flow-Shop scheduling problem: A literature review

Author

Listed:
  • Rossit, Daniel Alejandro
  • Tohmé, Fernando
  • Frutos, Mariano

Abstract

The Non-Permutation Flow-Shop scheduling problem (NPFS) is a generalization of the traditional Permutation Flow-Shop scheduling problem (PFS) that allows changes in the job order on different machines. The flexibility that NPFS provides in models for industrial applications justifies its use despite its combinatorial complexity. The literature on this problem has expanded largely in the last decade, indicating that the topic is an active research area. This review is a contribution towards the rationalization of the developments in the field, organizing them in terms of the objective functions in the different variants of the problem. A schematic presentation of both theoretical and experimental results summarizes many of the main advances in the study of NPFS. Finally, we include a bibliometric analysis, showing the most promising lines of future development.

Suggested Citation

  • Rossit, Daniel Alejandro & Tohmé, Fernando & Frutos, Mariano, 2018. "The Non-Permutation Flow-Shop scheduling problem: A literature review," Omega, Elsevier, vol. 77(C), pages 143-153.
    • Handle: RePEc:eee:jomega:v:77:y:2018:i:c:p:143-153
    DOI: 10.1016/j.omega.2017.05.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048316307289
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2017.05.010?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. Allahverdi, Ali, 2015. "The third comprehensive survey on scheduling problems with setup times/costs," European Journal of Operational Research, Elsevier, vol. 246(2), pages 345-378.
    2. 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.
    3. Benavides, Alexander J. & Ritt, Marcus & Miralles, Cristóbal, 2014. "Flow shop scheduling with heterogeneous workers," European Journal of Operational Research, Elsevier, vol. 237(2), pages 713-720.
    4. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    5. Aguezzoul, Aicha, 2014. "Third-party logistics selection problem: A literature review on criteria and methods," Omega, Elsevier, vol. 49(C), pages 69-78.
    6. Donya Rahmani & Reza Ramezanian & Mohammad Saidi-Mehrabad, 2014. "Multi-objective flow shop scheduling problem with stochastic parameters: fuzzy goal programming approach," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 21(3), pages 322-340.
    7. Viswanath Nagarajan & Maxim Sviridenko, 2009. "Tight Bounds for Permutation Flow Shop Scheduling," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 417-427, May.
    8. Ruiz, Rubén & Vázquez-Rodríguez, José Antonio, 2010. "The hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 1-18, August.
    9. Homa Amirian & Rashed Sahraeian, 2015. "Augmented ε-constraint method in multi-objective flowshop problem with past sequence set-up times and a modified learning effect," International Journal of Production Research, Taylor & Francis Journals, vol. 53(19), pages 5962-5976, October.
    10. M. Henneberg & J.S. Neufeld, 2016. "A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3534-3550, June.
    11. Koulamas, Christos, 1998. "A new constructive heuristic for the flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 105(1), pages 66-71, February.
    12. Ruiz, Ruben & Maroto, Concepcion & Alcaraz, Javier, 2005. "Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics," European Journal of Operational Research, Elsevier, vol. 165(1), pages 34-54, August.
    13. Aggoune, Riad, 2004. "Minimizing the makespan for the flow shop scheduling problem with availability constraints," European Journal of Operational Research, Elsevier, vol. 153(3), pages 534-543, March.
    14. Gerrit Farber & Anna M. Coves Moreno & Said Salhi, 2010. "Performance evaluation of hybrid-CLP vs. GA: non-permutation flowshop with constrained resequencing buffers," International Journal of Manufacturing Technology and Management, Inderscience Enterprises Ltd, vol. 20(1/2/3/4), pages 242-258.
    15. Nawaz, Muhammad & Enscore Jr, E Emory & Ham, Inyong, 1983. "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, Elsevier, vol. 11(1), pages 91-95.
    16. Rajendran, Chandrasekharan & Ziegler, Hans, 2001. "A performance analysis of dispatching rules and a heuristic in static flowshops with missing operations of jobs," European Journal of Operational Research, Elsevier, vol. 131(3), pages 622-634, June.
    17. Kis, Tamas, 2003. "Job-shop scheduling with processing alternatives," European Journal of Operational Research, Elsevier, vol. 151(2), pages 307-332, December.
    18. Demirkol, Ebru & Mehta, Sanjay & Uzsoy, Reha, 1998. "Benchmarks for shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 109(1), pages 137-141, August.
    19. Allahverdi, Ali & Gupta, Jatinder N. D. & Aldowaisan, Tariq, 1999. "A review of scheduling research involving setup considerations," Omega, Elsevier, vol. 27(2), pages 219-239, April.
    20. Mehravaran, Yasaman & Logendran, Rasaratnam, 2012. "Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 135(2), pages 953-963.
    21. Kis, Tamas & Pesch, Erwin, 2005. "A review of exact solution methods for the non-preemptive multiprocessor flowshop problem," European Journal of Operational Research, Elsevier, vol. 164(3), pages 592-608, August.
    22. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    23. Xiao, Yiyong & Yuan, Yingying & Zhang, Ren-Qian & Konak, Abdullah, 2015. "Non-permutation flow shop scheduling with order acceptance and weighted tardiness," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 312-333.
    24. Blazewicz, Jacek & Pesch, Erwin & Sterna, Malgorzata & Werner, Frank, 2005. "The two-machine flow-shop problem with weighted late work criterion and common due date," European Journal of Operational Research, Elsevier, vol. 165(2), pages 408-415, September.
    25. Taillard, E., 1993. "Benchmarks for basic scheduling problems," European Journal of Operational Research, Elsevier, vol. 64(2), pages 278-285, January.
    26. Jacek Błażewicz & Klaus H. Ecker & Erwin Pesch & Günter Schmidt & Jan Węglarz, 2007. "Handbook on Scheduling," International Handbooks on Information Systems, Springer, number 978-3-540-32220-7, November.
    27. 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.
    28. Behzad Nikjo & Yaser Zarook, 2014. "A Non-Permutation Flow Shop Manufacturing Cell Scheduling Problem with Part's Sequence Dependent Family Setup Times," International Journal of Applied Metaheuristic Computing (IJAMC), IGI Global, vol. 5(4), pages 70-86, October.
    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. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    2. Geser, Philine & Le, Hoang Thanh & Hartmann, Tom & Middendorf, Martin, 2022. "On permutation schedules for two-machine flow shops with buffer constraints and constant processing times on one machine," European Journal of Operational Research, Elsevier, vol. 303(2), pages 593-601.
    3. Alvarez-Meaza, Izaskun & Zarrabeitia-Bilbao, Enara & Rio-Belver, Rosa-María & Garechana-Anacabe, Gaizka, 2021. "Green scheduling to achieve green manufacturing: Pursuing a research agenda by mapping science," Technology in Society, Elsevier, vol. 67(C).
    4. Jin Qian & Haiyan Han, 2022. "Improved algorithms for proportionate flow shop scheduling with due-window assignment," Annals of Operations Research, Springer, vol. 309(1), pages 249-258, February.
    5. Zhang, Zhe & Gong, Xue & Song, Xiaoling & Yin, Yong & Lev, Benjamin & Chen, Jie, 2022. "A column generation-based exact solution method for seru scheduling problems," Omega, Elsevier, vol. 108(C).
    6. Liu, Yu & Zhang, Qin & Ouyang, Zhiyuan & Huang, Hong-Zhong, 2021. "Integrated production planning and preventive maintenance scheduling for synchronized parallel machines," Reliability Engineering and System Safety, Elsevier, vol. 215(C).
    7. Long Peng & Jiajie Li & Jingming Zhao & Sanlei Dang & Zhengmin Kong & Li Ding, 2022. "Automatic Verification Flow Shop Scheduling of Electric Energy Meters Based on an Improved Q-Learning Algorithm," Energies, MDPI, vol. 15(5), pages 1-11, February.
    8. Chen, Wenchong & Gong, Xuejian & Rahman, Humyun Fuad & Liu, Hongwei & Qi, Ershi, 2021. "Real-time order acceptance and scheduling for data-enabled permutation flow shops: Bilevel interactive optimization with nonlinear integer programming," Omega, Elsevier, vol. 105(C).
    9. Javad Seif & Mohammad Dehghanimohammadabadi & Andrew Junfang Yu, 2020. "Integrated preventive maintenance and flow shop scheduling under uncertainty," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 852-887, December.
    10. Rossit, Daniel A. & Vásquez, Óscar C. & Tohmé, Fernando & Frutos, Mariano & Safe, Martín D., 2021. "A combinatorial analysis of the permutation and non-permutation flow shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 289(3), pages 841-854.
    11. Mohamed Amine Mkadem & Aziz Moukrim & Mehdi Serairi, 2021. "Exact method for the two-machine flow-shop problem with time delays," Annals of Operations Research, Springer, vol. 298(1), pages 375-406, March.

    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. Meenakshi Sharma & Manisha Sharma & Sameer Sharma, 2022. "Desert sparrow optimization algorithm for the bicriteria flow shop scheduling problem with sequence-independent setup time," Operational Research, Springer, vol. 22(4), pages 4353-4396, September.
    2. Fátima Pilar & Eliana Costa e Silva & Ana Borges, 2023. "Optimizing Vehicle Repairs Scheduling Using Mixed Integer Linear Programming: A Case Study in the Portuguese Automobile Sector," Mathematics, MDPI, vol. 11(11), pages 1-23, June.
    3. Smutnicki, Czeslaw & Pempera, Jaroslaw & Bocewicz, Grzegorz & Banaszak, Zbigniew, 2022. "Cyclic flow-shop scheduling with no-wait constraints and missing operations," European Journal of Operational Research, Elsevier, vol. 302(1), pages 39-49.
    4. Sioud, A. & Gagné, C., 2018. "Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 264(1), pages 66-73.
    5. M. Henneberg & J.S. Neufeld, 2016. "A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3534-3550, June.
    6. Ciavotta, Michele & Minella, Gerardo & Ruiz, Rubén, 2013. "Multi-objective sequence dependent setup times permutation flowshop: A new algorithm and a comprehensive study," European Journal of Operational Research, Elsevier, vol. 227(2), pages 301-313.
    7. S Afshin Mansouri & Emel Aktas, 2016. "Minimizing energy consumption and makespan in a two-machine flowshop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(11), pages 1382-1394, November.
    8. Benavides, Alexander J. & Ritt, Marcus & Miralles, Cristóbal, 2014. "Flow shop scheduling with heterogeneous workers," European Journal of Operational Research, Elsevier, vol. 237(2), pages 713-720.
    9. Missaoui, Ahmed & Ruiz, Rubén, 2022. "A parameter-Less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows," European Journal of Operational Research, Elsevier, vol. 303(1), pages 99-113.
    10. Michał Ćwik & Jerzy Józefczyk, 2018. "Heuristic algorithms for the minmax regret flow-shop problem with interval processing times," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 26(1), pages 215-238, March.
    11. Allahverdi, Ali, 2016. "A survey of scheduling problems with no-wait in process," European Journal of Operational Research, Elsevier, vol. 255(3), pages 665-686.
    12. Dominik Kress & David Müller & Jenny Nossack, 2019. "A worker constrained flexible job shop scheduling problem with sequence-dependent setup times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 179-217, March.
    13. Dominik Kress & Maksim Barketau & Erwin Pesch, 2018. "Single-machine batch scheduling to minimize the total setup cost in the presence of deadlines," Journal of Scheduling, Springer, vol. 21(6), pages 595-606, December.
    14. Weng, Wei & Fujimura, Shigeru, 2012. "Control methods for dynamic time-based manufacturing under customized product lead times," European Journal of Operational Research, Elsevier, vol. 218(1), pages 86-96.
    15. Shahvari, Omid & Logendran, Rasaratnam, 2016. "Hybrid flow shop batching and scheduling with a bi-criteria objective," International Journal of Production Economics, Elsevier, vol. 179(C), pages 239-258.
    16. Hinder, Oliver & Mason, Andrew J., 2017. "A novel integer programing formulation for scheduling with family setup times on a single machine to minimize maximum lateness," European Journal of Operational Research, Elsevier, vol. 262(2), pages 411-423.
    17. Kalczynski, Pawel Jan & Kamburowski, Jerzy, 2007. "On the NEH heuristic for minimizing the makespan in permutation flow shops," Omega, Elsevier, vol. 35(1), pages 53-60, February.
    18. Waldherr, Stefan & Knust, Sigrid, 2017. "Decomposition algorithms for synchronous flow shop problems with additional resources and setup times," European Journal of Operational Research, Elsevier, vol. 259(3), pages 847-863.
    19. Pan, Quan-Ke & Gao, Liang & Li, Xin-Yu & Gao, Kai-Zhou, 2017. "Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 303(C), pages 89-112.
    20. Dirk Briskorn & Konrad Stephan & Nils Boysen, 2022. "Minimizing the makespan on a single machine subject to modular setups," Journal of Scheduling, Springer, vol. 25(1), pages 125-137, February.

    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:eee:jomega:v:77:y:2018:i:c:p:143-153. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    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.