IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v282y2020i2p478-490.html
   My bibliography  Save this article

Flow shops with reentry: Reversibility properties and makespan optimal schedules

Author

Listed:
  • Yu, Tae-Sun
  • Pinedo, Michael

Abstract

We consider flow shops with job reentry. We first discuss how reversibility properties of conventional flow shops can be generalized to flow shop models with job reentry. We show under which conditions the makespan and job flow times are reversible. Second, we examine the problem of minimizing the makespan in ordered flow shops with job reentry. In particular, we focus on two special cases of the ordered flow shop that are referred to as machine-ordered and proportionate flow shops. We specify a class of cyclic schedules that have a makespan invariance property and minimize the makespan when each job follows the same route. We then examine makespan optimal schedules in a more generalized processing environment with loop effects on job processing times for which the makespan invariance property does not hold. Lastly, we present a dispatching rule that minimizes the makespan when considering a more general form of job recirculation with the route of each job not necessarily being the same.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:282:y:2020:i:2:p:478-490
    DOI: 10.1016/j.ejor.2019.09.036
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719307933
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2019.09.036?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. M. L. Smith & S. S. Panwalkar & R. A. Dudek, 1975. "Flowshop Sequencing Problem with Ordered Processing Time Matrices," Management Science, INFORMS, vol. 21(5), pages 544-549, January.
    2. Ribas, Imma & Companys, Ramon & Tort-Martorell, Xavier, 2011. "An iterated greedy algorithm for the flowshop scheduling problem with blocking," Omega, Elsevier, vol. 39(3), pages 293-301, June.
    3. 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.
    4. Graves, Stephen C., 1983. "Scheduling of re-entrant flow shops," Working papers 1438-83., Massachusetts Institute of Technology (MIT), Sloan School of Management.
    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. Michael Pinedo, 1985. "A Note on Stochastic Shop Models in Which Jobs have the Same Processing Requirements on Each Machine," Management Science, INFORMS, vol. 31(7), pages 840-846, July.
    7. Eginhard J. Muth, 1979. "The Reversibility Property of Production Lines," Management Science, INFORMS, vol. 25(2), pages 152-158, February.
    8. Koulamas, Christos & Kyparisis, George J., 2015. "The three-machine proportionate open shop and mixed shop minimum makespan problems," European Journal of Operational Research, Elsevier, vol. 243(1), pages 70-74.
    9. Christos Koulamas, 1994. "The Total Tardiness Problem: Review and Extensions," Operations Research, INFORMS, vol. 42(6), pages 1025-1041, December.
    10. Lawrence M. Wein & Philippe B. Chevalier, 1992. "A Broader View of the Job-Shop Scheduling Problem," Management Science, INFORMS, vol. 38(7), pages 1018-1033, July.
    11. M. Y. Wang & S. P. Sethi & S. L. van de Velde, 1997. "Minimizing Makespan in a Class of Reentrant Shops," Operations Research, INFORMS, vol. 45(5), pages 702-712, October.
    12. Peng Si Ow, 1985. "Focused Scheduling in Proportionate Flowshops," Management Science, INFORMS, vol. 31(7), pages 852-869, July.
    13. M. R. Garey & D. S. Johnson & Ravi Sethi, 1976. "The Complexity of Flowshop and Jobshop Scheduling," Mathematics of Operations Research, INFORMS, vol. 1(2), pages 117-129, May.
    14. S.S. Panwalkar & Milton L. Smith & Christos Koulamas, 2013. "Review of the ordered and proportionate flow shop scheduling research," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 46-55, February.
    15. Michael Pinedo, 1982. "Minimizing the Expected Makespan in Stochastic Flow Shops," Operations Research, INFORMS, vol. 30(1), pages 148-162, February.
    16. Wieslaw Kubiak & Sheldon X. C. Lou & Yingmeng Wang, 1996. "Mean Flow Time Minimization in Reentrant Job Shops with a Hub," Operations Research, INFORMS, vol. 44(5), pages 764-776, 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. Benavides, Alexander J. & Vera, Antony, 2022. "The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(2), pages 407-421.
    2. Wu, Kan & Huang, Edward & Wang, Mengchang & Zheng, Meimei, 2022. "Job scheduling of diffusion furnaces in semiconductor fabrication facilities," European Journal of Operational Research, Elsevier, vol. 301(1), pages 141-152.

    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. 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.
    2. S.S. Panwalkar & Christos Koulamas, 2015. "Proportionate flow shop: New complexity results and models with due date assignment," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(2), pages 98-106, March.
    3. Lee, Kangbok & Zheng, Feifeng & Pinedo, Michael L., 2019. "Online scheduling of ordered flow shops," European Journal of Operational Research, Elsevier, vol. 272(1), pages 50-60.
    4. 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.
    5. S.S. Panwalkar & Milton L. Smith & Christos Koulamas, 2013. "Review of the ordered and proportionate flow shop scheduling research," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(1), pages 46-55, February.
    6. Byung-Cheon Choi & Joseph Y.-T. Leung & Michael L. Pinedo, 2011. "Minimizing makespan in an ordered flow shop with machine-dependent processing times," Journal of Combinatorial Optimization, Springer, vol. 22(4), pages 797-818, November.
    7. 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.
    8. 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.
    9. 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.
    10. S.S. Panwalkar & Christos Koulamas, 2015. "On equivalence between the proportionate flow shop and single‐machine scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 62(7), pages 595-603, October.
    11. Kamburowski, Jerzy, 1999. "Stochastically minimizing the makespan in two-machine flow shops without blocking," European Journal of Operational Research, Elsevier, vol. 112(2), pages 304-309, January.
    12. Choi, Byung-Cheon & Lee, Kangbok & Leung, Joseph Y.-T. & Pinedo, Michael L., 2010. "Flow shops with machine maintenance: Ordered and proportionate cases," European Journal of Operational Research, Elsevier, vol. 207(1), pages 97-104, November.
    13. Choi, Byung-Cheon & Chung, Jibok, 2011. "Two-machine flow shop scheduling problem with an outsourcing option," European Journal of Operational Research, Elsevier, vol. 213(1), pages 66-72, August.
    14. P J Kalczynski & J Kamburowski, 2004. "Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(12), pages 1358-1362, December.
    15. 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.
    16. 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.
    17. Choi, Byung-Cheon & Yoon, Suk-Hun & Chung, Sung-Jin, 2007. "Minimizing maximum completion time in a proportionate flow shop with one machine of different speed," European Journal of Operational Research, Elsevier, vol. 176(2), pages 964-974, January.
    18. Christoph Hertrich & Christian Weiß & Heiner Ackermann & Sandy Heydrich & Sven O. Krumke, 2020. "Scheduling a proportionate flow shop of batching machines," Journal of Scheduling, Springer, vol. 23(5), pages 575-593, October.
    19. Shi-Sheng Li & De-Liang Qian & Ren-Xia Chen, 2017. "Proportionate Flow Shop Scheduling with Rejection," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-13, August.
    20. Ding, Jian-Ya & Song, Shiji & Wu, Cheng, 2016. "Carbon-efficient scheduling of flow shops by multi-objective optimization," European Journal of Operational Research, Elsevier, vol. 248(3), pages 758-771.

    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:ejores:v:282:y:2020:i:2:p:478-490. 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/locate/eor .

    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.