IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v89y2024i2d10.1007_s10898-023-01354-0.html
   My bibliography  Save this article

Single-lot, lot-streaming problem for a 1 + m hybrid flow shop

Author

Listed:
  • Sanchit Singh

    (Virginia Tech)

  • Subhash C. Sarin

    (Virginia Tech)

  • Ming Cheng

    (Soochow University)

Abstract

In this paper, we consider an application of lot-streaming for processing a lot of multiple items in a hybrid flow shop (HFS) for the objective of minimizing makespan. The HFS that we consider consists of two stages with a single machine available for processing in Stage 1 and m identical parallel machines in Stage 2. We call this problem a 1 + m TSHFS-LSP (two-stage hybrid flow shop, lot streaming problem), and show it to be NP-hard in general, except for the case when the sublot sizes are treated to be continuous. The novelty of our work is in obtaining closed-form expressions for optimal continuous sublot sizes that can be solved in polynomial time, for a given number of sublots. A fast linear search algorithm is also developed for determining the optimal number of sublots for the case of continuous sublot sizes. For the case when the sublot sizes are discrete, we propose a branch-and-bound-based heuristic to determine both the number of sublots and sublot sizes and demonstrate its efficacy by comparing its performance against that of a direct solution of a mixed-integer formulation of the problem by CPLEX®.

Suggested Citation

  • Sanchit Singh & Subhash C. Sarin & Ming Cheng, 2024. "Single-lot, lot-streaming problem for a 1 + m hybrid flow shop," Journal of Global Optimization, Springer, vol. 89(2), pages 435-455, June.
    • Handle: RePEc:spr:jglopt:v:89:y:2024:i:2:d:10.1007_s10898-023-01354-0
    DOI: 10.1007/s10898-023-01354-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-023-01354-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/s10898-023-01354-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. Hoogeveen, J. A. & Lenstra, J. K. & Veltman, B., 1996. "Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard," European Journal of Operational Research, Elsevier, vol. 89(1), pages 172-175, February.
    2. Vickson, R. G., 1995. "Optimal lot streaming for multiple products in a two-machine flow shop," European Journal of Operational Research, Elsevier, vol. 85(3), pages 556-575, September.
    3. Robert J. Wittrock, 1988. "An Adaptable Scheduling Algorithm for Flexible Flow Lines," Operations Research, INFORMS, vol. 36(3), pages 445-453, June.
    4. Liu, Jiyin, 2008. "Single-job lot streaming in m - 1 two-stage hybrid flowshops," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1171-1183, June.
    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. 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.
    2. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    3. Tzu-Li Chen & Chen-Yang Cheng & Yi-Han Chou, 2020. "Multi-objective genetic algorithm for energy-efficient hybrid flow shop scheduling with lot streaming," Annals of Operations Research, Springer, vol. 290(1), pages 813-836, July.
    4. Lin, Hung-Tso & Liao, Ching-Jong, 2003. "A case study in a two-stage hybrid flow shop with setup time and dedicated machines," International Journal of Production Economics, Elsevier, vol. 86(2), pages 133-143, November.
    5. Vo[ss], Stefan & Witt, Andreas, 2007. "Hybrid flow shop scheduling as a multi-mode multi-project scheduling problem with batching requirements: A real-world application," International Journal of Production Economics, Elsevier, vol. 105(2), pages 445-458, February.
    6. Djellab, Housni & Djellab, Khaled, 2002. "Preemptive Hybrid Flowshop Scheduling problem of interval orders," European Journal of Operational Research, Elsevier, vol. 137(1), pages 37-49, February.
    7. Chiu, Huan Neng & Chang, Jen Huei, 2005. "Cost models for lot streaming in a multistage flow shop," Omega, Elsevier, vol. 33(5), pages 435-450, October.
    8. A. G. Leeftink & R. J. Boucherie & E. W. Hans & M. A. M. Verdaasdonk & I. M. H. Vliegen & P. J. Diest, 2018. "Batch scheduling in the histopathology laboratory," Flexible Services and Manufacturing Journal, Springer, vol. 30(1), pages 171-197, June.
    9. Li, Shanling, 1997. "A hybrid two-stage flowshop with part family, batch production, major and minor set-ups," European Journal of Operational Research, Elsevier, vol. 102(1), pages 142-156, October.
    10. Figielska, Ewa, 2014. "A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages," European Journal of Operational Research, Elsevier, vol. 236(2), pages 433-444.
    11. Kamran Kianfar & Arezoo Atighehchian, 2023. "A hybrid heuristic approach to master surgery scheduling with downstream resource constraints and dividable operating room blocks," Annals of Operations Research, Springer, vol. 328(1), pages 727-754, September.
    12. D Biskup & M Feldmann, 2006. "Lot streaming with variable sublots: an integer programming formulation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 57(3), pages 296-303, March.
    13. Niu, Qun & Zhou, Taijin & Fei, Minrui & Wang, Bing, 2012. "An efficient quantum immune algorithm to minimize mean flow time for hybrid flow shop problems," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 84(C), pages 1-25.
    14. Mohamed Haouari & Lotfi Hidri & Anis Gharbi, 2006. "Optimal Scheduling of a Two-stage Hybrid Flow Shop," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 64(1), pages 107-124, August.
    15. C. A. Glass & C. N. Potts, 1998. "Structural Properties of Lot Streaming in a Flow Shop," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 624-639, August.
    16. Santos, D. L. & Hunsucker, J. L. & Deal, D. E., 1995. "Global lower bounds for flow shops with multiple processors," European Journal of Operational Research, Elsevier, vol. 80(1), pages 112-120, January.
    17. Joaquín Bautista-Valhondo & Rocío Alfaro-Pozo, 2020. "Mixed integer linear programming models for Flow Shop Scheduling with a demand plan of job types," 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. 28(1), pages 5-23, March.
    18. 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.
    19. Zhang, Wei & Yin, Changyu & Liu, Jiyin & Linn, Richard J., 2005. "Multi-job lot streaming to minimize the mean completion time in m-1 hybrid flowshops," International Journal of Production Economics, Elsevier, vol. 96(2), pages 189-200, May.
    20. Negenman, Ebbe G., 2001. "Local search algorithms for the multiprocessor flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 128(1), pages 147-158, January.

    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:jglopt:v:89:y:2024:i:2:d:10.1007_s10898-023-01354-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.