IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v21y2018i2d10.1007_s10951-017-0529-x.html
   My bibliography  Save this article

Family scheduling with batch availability in flow shops to minimize makespan

Author

Listed:
  • Liji Shen

    (WHU – Otto Beisheim School of Management)

  • Jatinder N. D. Gupta

    (University of Alabama in Huntsville)

Abstract

This paper addresses a batch scheduling problem in flow shop production systems, where job families are formed based on setup similarities. In order to improve setup efficiency, we consider batching decisions in our solution procedure. Due to its high practical relevance, the batch availability assumption is also adopted in this study. In the presence of sequence-dependent setup times, it is proved that a permutation flow shop is generally not optimal. Therefore, our objective is to determine solutions with inconsistent batches, which essentially lead to non-permutation schedules, to minimize makespan. After examining structural properties, we develop a tabu search algorithm with multiple neighbourhood functions. Computational results confirm the remarkable benefits of batching decisions. Our algorithm also outperforms some well-known and well-performing approaches.

Suggested Citation

  • Liji Shen & Jatinder N. D. Gupta, 2018. "Family scheduling with batch availability in flow shops to minimize makespan," Journal of Scheduling, Springer, vol. 21(2), pages 235-249, April.
    • Handle: RePEc:spr:jsched:v:21:y:2018:i:2:d:10.1007_s10951-017-0529-x
    DOI: 10.1007/s10951-017-0529-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-017-0529-x
    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/s10951-017-0529-x?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. Mosheiov, Gur & Oron, Daniel, 2008. "Open-shop batch scheduling with identical jobs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1282-1292, June.
    2. Hamed Hendizadeh, S. & Faramarzi, Hamidreza & Mansouri, S.Afshin & Gupta, Jatinder N.D. & Y ElMekkawy, Tarek, 2008. "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times," International Journal of Production Economics, Elsevier, vol. 111(2), pages 593-605, February.
    3. Herbert G. Campbell & Richard A. Dudek & Milton L. Smith, 1970. "A Heuristic Algorithm for the n Job, m Machine Sequencing Problem," Management Science, INFORMS, vol. 16(10), pages 630-637, June.
    4. Buscher, Udo & Shen, Liji, 2009. "An integrated tabu search algorithm for the lot streaming problem in job shops," European Journal of Operational Research, Elsevier, vol. 199(2), pages 385-399, December.
    5. Eugeniusz Nowicki & Czeslaw Smutnicki, 1996. "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, INFORMS, vol. 42(6), pages 797-813, June.
    6. Mosheiov, Gur & Oron, Daniel, 2005. "A note on flow-shop and job-shop batch scheduling with identical processing-time jobs," European Journal of Operational Research, Elsevier, vol. 161(1), pages 285-291, February.
    7. J.S. Neufeld & J.N.D. Gupta & U. Buscher, 2015. "Minimising makespan in flowshop group scheduling with sequence-dependent family set-up times using inserted idle times," International Journal of Production Research, Taylor & Francis Journals, vol. 53(6), pages 1791-1806, March.
    8. Logendran, Rasaratnam & deSzoeke, Paula & Barnard, Faith, 2006. "Sequence-dependent group scheduling problems in flexible flow shops," International Journal of Production Economics, Elsevier, vol. 102(1), pages 66-86, July.
    9. Roberto Battiti & Giampietro Tecchiolli, 1994. "The Reactive Tabu Search," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 126-140, May.
    10. Cheng, T. C. Edwin & Gordon, Valery S. & Kovalyov, Mikhail Y., 1996. "Single machine scheduling with batch deliveries," European Journal of Operational Research, Elsevier, vol. 94(2), pages 277-283, October.
    11. Gupta, Jatinder N.D. & Stafford, Edward Jr., 2006. "Flowshop scheduling research after five decades," European Journal of Operational Research, Elsevier, vol. 169(3), pages 699-711, March.
    12. Sung, Chang Sup & Kim, Young Hwan & Yoon, Sang Hum, 2000. "A problem reduction and decomposition approach for scheduling for a flowshop of batch processing machines," European Journal of Operational Research, Elsevier, vol. 121(1), pages 179-192, February.
    13. 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.
    14. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    15. van Hoesel, Stan & Wagelmans, Albert & Moerman, Bram, 1994. "Using geometric techniques to improve dynamic programming algorithms for the economic lot-sizing problem and extensions," European Journal of Operational Research, Elsevier, vol. 75(2), pages 312-331, June.
    16. Scott Webster & Kenneth R. Baker, 1995. "Scheduling Groups of Jobs on a Single Machine," Operations Research, INFORMS, vol. 43(4), pages 692-703, August.
    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. Shen, Liji & Buscher, Udo, 2012. "Solving the serial batching problem in job shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 221(1), pages 14-26.
    2. Matin, Hossein N.Z. & Salmasi, Nasser & Shahvari, Omid, 2017. "Makespan minimization in flowshop batch processing problem with different batch compositions on machines," International Journal of Production Economics, Elsevier, vol. 193(C), pages 832-844.
    3. Shen, Liji & Dauzère-Pérès, Stéphane & Maecker, Söhnke, 2023. "Energy cost efficient scheduling in flexible job-shop manufacturing systems," European Journal of Operational Research, Elsevier, vol. 310(3), pages 992-1016.
    4. B. M. T. Lin & T. C. E. Cheng, 2011. "Scheduling with centralized and decentralized batching policies in concurrent open shops," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(1), pages 17-27, February.
    5. Shen, Liji & Dauzère-Pérès, Stéphane & Neufeld, Janis S., 2018. "Solving the flexible job shop scheduling problem with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 265(2), pages 503-516.
    6. Amin-Naseri, Mohammad Reza & Beheshti-Nia, Mohammad Ali, 2009. "Hybrid flow shop scheduling with parallel batching," International Journal of Production Economics, Elsevier, vol. 117(1), pages 185-196, January.
    7. Buscher, Udo & Shen, Liji, 2009. "An integrated tabu search algorithm for the lot streaming problem in job shops," European Journal of Operational Research, Elsevier, vol. 199(2), pages 385-399, December.
    8. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    9. Xiangtong Qi, 2005. "A logistics scheduling model: Inventory cost reduction by batching," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 312-320, June.
    10. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    11. Chang, Yung-Chia & Lee, Chung-Yee, 2004. "Machine scheduling with job delivery coordination," European Journal of Operational Research, Elsevier, vol. 158(2), pages 470-487, October.
    12. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    13. Abdeljaouad, Mohamed Amine & Bahroun, Zied & Omrane, Anissa & Fondrevelle, Julien, 2015. "Job-shop production scheduling with reverse flows," European Journal of Operational Research, Elsevier, vol. 244(1), pages 117-128.
    14. Esaignani Selvarajah & George Steiner, 2009. "Approximation Algorithms for the Supplier's Supply Chain Scheduling Problem to Minimize Delivery and Inventory Holding Costs," Operations Research, INFORMS, vol. 57(2), pages 426-438, April.
    15. X Wang & L Tang, 2011. "Scheduling a single machine with multiple job processing ability to minimize makespan," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(8), pages 1555-1565, August.
    16. Jae-Min Yu & Rong Huang & Dong-Ho Lee, 2017. "Iterative algorithms for batching and scheduling to minimise the total job tardiness in two-stage hybrid flow shops," International Journal of Production Research, Taylor & Francis Journals, vol. 55(11), pages 3266-3282, June.
    17. Drótos, Márton & Erdos, Gábor & Kis, Tamás, 2009. "Computing lower and upper bounds for a large-scale industrial job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 197(1), pages 296-306, August.
    18. 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.
    19. Mazdeh, Mohammad Mahdavi & Sarhadi, Mansoor & Hindi, Khalil S., 2007. "A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs," European Journal of Operational Research, Elsevier, vol. 183(1), pages 74-86, November.
    20. Li, Guo & Li, Na & Sambandam, Narayanasamy & Sethi, Suresh P. & Zhang, Faping, 2018. "Flow shop scheduling with jobs arriving at different times," International Journal of Production Economics, Elsevier, vol. 206(C), pages 250-260.

    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:jsched:v:21:y:2018:i:2:d:10.1007_s10951-017-0529-x. 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.