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. 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.
    2. Graves, Stephen C., 1983. "Scheduling of re-entrant flow shops," Working papers 1438-83., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    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. 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.
    11. 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.
    12. 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.
    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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Konstantinos S. Boulas & Georgios D. Dounias & Chrissoleon T. Papadopoulos, 2023. "A hybrid evolutionary algorithm approach for estimating the throughput of short reliable approximately balanced production lines," Journal of Intelligent Manufacturing, Springer, vol. 34(2), pages 823-852, February.
    13. Yazdani Sabouni, M.T. & Logendran, Rasaratnam, 2013. "Carryover sequence-dependent group scheduling with the integration of internal and external setup times," European Journal of Operational Research, Elsevier, vol. 224(1), pages 8-22.
    14. Hasani, Ali & Hosseini, Seyed Mohammad Hassan, 2020. "A bi-objective flexible flow shop scheduling problem with machine-dependent processing stages: Trade-off between production costs and energy consumption," Applied Mathematics and Computation, Elsevier, vol. 386(C).
    15. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    16. Klamroth, Kathrin & Köbis, Elisabeth & Schöbel, Anita & Tammer, Christiane, 2017. "A unified approach to uncertain optimization," European Journal of Operational Research, Elsevier, vol. 260(2), pages 403-420.
    17. 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.
    18. Fan Yang & Roel Leus, 2021. "Scheduling hybrid flow shops with time windows," Journal of Heuristics, Springer, vol. 27(1), pages 133-158, April.
    19. Tim Holzmann & J. Cole Smith, 2019. "Shortest path interdiction problem with arc improvement recourse: A multiobjective approach," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(3), pages 230-252, April.
    20. Mut, Murat & Wiecek, Margaret M., 2011. "Generalized equitable preference in multiobjective programming," European Journal of Operational Research, Elsevier, vol. 212(3), pages 535-551, August.

    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.