IDEAS home Printed from https://ideas.repec.org/a/spr/operea/v23y2023i2d10.1007_s12351-023-00770-0.html
   My bibliography  Save this article

A bi-objective re-entrant permutation flow shop scheduling problem: minimizing the makespan and maximum tardiness

Author

Listed:
  • Maedeh Fasihi

    (University of Tehran)

  • Reza Tavakkoli-Moghaddam

    (University of Tehran)

  • Fariborz Jolai

    (University of Tehran)

Abstract

This paper addresses a re-entrant permutation flow shop (RPFS) scheduling problem that minimizes the makespan and maximum tardiness of jobs and presents a two-step procedure. In the first step, a population is broken down into sub-populations, in which a genetic algorithm (GA) is applied to obtain an appropriate approximation of a Pareto front. In the second step, non-dominant solutions are unified as a single large population to enhance the Pareto-front. A multi-objective hybrid meta-heuristic algorithm is proposed based on a dominance relation. In general, proper combinations of multi-objective approaches are considered in two steps that combine elements of both GA and simulated annealing (SA). A hybrid meta-heuristic algorithm is used for raising the generality level. Thus, the same solution approach can be applied to various problems. The hybrid meta-heuristic algorithm is considered with Lorenz dominance and Pareto dominance separately. Three approaches are used to assess non-dominated solution sets. Afterward, a comparison between non-dominated sets taken from each step and non-dominated sorting genetic algorithm (NSGA-II) and Lorenz NSGA-II (LNSGA-II) algorithms proposed in the previous studies is carried out. The two-step algorithm is an effective method for this study, according to the computational research findings. Moreover, applying the set coverage criterion shows the superiority of Lorenz dominance over Pareto dominance relations.

Suggested Citation

  • Maedeh Fasihi & Reza Tavakkoli-Moghaddam & Fariborz Jolai, 2023. "A bi-objective re-entrant permutation flow shop scheduling problem: minimizing the makespan and maximum tardiness," Operational Research, Springer, vol. 23(2), pages 1-41, June.
    • Handle: RePEc:spr:operea:v:23:y:2023:i:2:d:10.1007_s12351-023-00770-0
    DOI: 10.1007/s12351-023-00770-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s12351-023-00770-0
    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/s12351-023-00770-0?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. Chettha Chamnanlor & Kanchana Sethanan & Mitsuo Gen & Chen-Fu Chien, 2017. "Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints," Journal of Intelligent Manufacturing, Springer, vol. 28(8), pages 1915-1931, December.
    2. Patrice Perny & Olivier Spanjaard & Louis-Xavier Storme, 2006. "A decision-theoretic approach to robust optimization in multivalued graphs," Annals of Operations Research, Springer, vol. 147(1), pages 317-341, October.
    3. Chang, Pei-Chann & Hsieh, Jih-Chang & Lin, Shui-Geng, 2002. "The development of gradual-priority weighting approach for the multi-objective flowshop scheduling problem," International Journal of Production Economics, Elsevier, vol. 79(3), pages 171-183, October.
    4. Karim Amrouche & Mourad Boudhar & Nazim Sami, 2020. "Two-machine chain-reentrant flow shop with the no-wait constraint," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 14(4), pages 573-597.
    5. Yang, Dar-Li & Kuo, Wen-Hung & Chern, Maw-Sheng, 2008. "Multi-family scheduling in a two-machine reentrant flow shop with setups," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1160-1170, June.
    6. S. M. Mousavi & I. Mahdavi & J. Rezaeian & M. Zandieh, 2018. "An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times," Operational Research, Springer, vol. 18(1), pages 123-158, April.
    7. Graves, Stephen C., 1983. "Scheduling of re-entrant flow shops," Working papers 1438-83., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    8. Choi, Seong-Woo & Kim, Yeong-Dae, 2009. "Minimizing total tardiness on a two-machine re-entrant flowshop," European Journal of Operational Research, Elsevier, vol. 199(2), pages 375-384, December.
    9. Xiang Yi Zhang & Lu Chen, 2018. "A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 56(16), pages 5293-5305, August.
    10. Jing-nan Shen & Ling Wang & Huan-yu Zheng, 2016. "A modified teaching--learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(12), pages 3622-3639, June.
    11. Dugardin, Frédéric & Yalaoui, Farouk & Amodeo, Lionel, 2010. "New multi-objective method to solve reentrant hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 22-31, May.
    12. Kaifeng Geng & Chunming Ye & Zhen hua Dai & Li Liu, 2020. "Bi-Objective Re-Entrant Hybrid Flow Shop Scheduling considering Energy Consumption Cost under Time-of-Use Electricity Tariffs," Complexity, Hindawi, vol. 2020, pages 1-17, February.
    Full references (including those not matched with items on IDEAS)

    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. Neufeld, Janis S. & Schulz, Sven & Buscher, Udo, 2023. "A systematic review of multi-objective hybrid flow shop scheduling," European Journal of Operational Research, Elsevier, vol. 309(1), pages 1-23.
    2. Yu, Tae-Sun & Pinedo, Michael, 2020. "Flow shops with reentry: Reversibility properties and makespan optimal schedules," European Journal of Operational Research, Elsevier, vol. 282(2), pages 478-490.
    3. Dugardin, Frédéric & Yalaoui, Farouk & Amodeo, Lionel, 2010. "New multi-objective method to solve reentrant hybrid flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 22-31, May.
    4. Lei Liu & Marcello Urgo, 2024. "Robust scheduling in a two-machine re-entrant flow shop to minimise the value-at-risk of the makespan: branch-and-bound and heuristic algorithms based on Markovian activity networks and phase-type dis," Annals of Operations Research, Springer, vol. 338(1), pages 741-764, July.
    5. Choi, Seong-Woo & Kim, Yeong-Dae, 2009. "Minimizing total tardiness on a two-machine re-entrant flowshop," European Journal of Operational Research, Elsevier, vol. 199(2), pages 375-384, December.
    6. Wenjuan Fan & Yi Wang & Tongzhu Liu & Guixian Tong, 2020. "A patient flow scheduling problem in ophthalmology clinic solved by the hybrid EDA–VNS algorithm," Journal of Combinatorial Optimization, Springer, vol. 39(2), pages 547-580, February.
    7. Hongtao Tang & Jiahao Zhou & Yiping Shao & Zhixiong Yang, 2023. "Hybrid Flow-Shop Scheduling Problems with Missing and Re-Entrant Operations Considering Process Scheduling and Production of Energy Consumption," Sustainability, MDPI, vol. 15(10), pages 1-19, May.
    8. Julio Mar-Ortiz & Alex J. Ruiz Torres & Belarmino Adenso-Díaz, 2022. "Scheduling in parallel machines with two objectives: analysis of factors that influence the Pareto frontier," Operational Research, Springer, vol. 22(4), pages 4585-4605, September.
    9. S-W Choi & Y-D Kim, 2007. "Minimizing makespan on a two-machine re-entrant flowshop," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(7), pages 972-981, July.
    10. Gheisariha, Elmira & Tavana, Madjid & Jolai, Fariborz & Rabiee, Meysam, 2021. "A simulation–optimization model for solving flexible flow shop scheduling problems with rework and transportation," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 180(C), pages 152-178.
    11. Jérémie Gallien & Stephen C. Graves & Alan Scheller-Wolf, 2016. "OM Forum—Practice-Based Research in Operations Management: What It Is, Why Do It, Related Challenges, and How to Overcome Them," Manufacturing & Service Operations Management, INFORMS, vol. 18(1), pages 5-14, February.
    12. 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.
    13. Jonas Ide & Anita Schöbel, 2016. "Robustness for uncertain multi-objective optimization: a survey and analysis of different concepts," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(1), pages 235-271, January.
    14. Nazim Sami & Karim Amrouche & Mourad Boudhar, 2024. "New efficient algorithms for the two-machine no-wait chain-reentrant shop problem," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-29, July.
    15. Bozorgirad, Mir Abbas & Logendran, Rasaratnam, 2013. "Bi-criteria group scheduling in hybrid flowshops," International Journal of Production Economics, Elsevier, vol. 145(2), pages 599-612.
    16. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    17. Karsu, Özlem & Morton, Alec, 2015. "Inequity averse optimization in operational research," European Journal of Operational Research, Elsevier, vol. 245(2), pages 343-359.
    18. Cheng, Mingbao & Tadikamalla, Pandu R. & Shang, Jennifer & Zhang, Shaqing, 2014. "Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs," European Journal of Operational Research, Elsevier, vol. 234(3), pages 650-657.
    19. Catanzaro, Daniele & Pesenti, Raffaele & Ronco, Roberto, 2021. "Job Scheduling under Time-of-Use Energy Tariffs for Sustainable Manufacturing: A Survey," LIDAM Discussion Papers CORE 2021019, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Zheng, Huan-yu & Wang, Ling, 2015. "Reduction of carbon emissions and project makespan by a Pareto-based estimation of distribution algorithm," International Journal of Production Economics, Elsevier, vol. 164(C), pages 421-432.

    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:operea:v:23:y:2023:i:2:d:10.1007_s12351-023-00770-0. 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.