IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v335y2024i1d10.1007_s10479-024-05860-6.html
   My bibliography  Save this article

A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops

Author

Listed:
  • Mingyang Gong

    (University of Alberta)

  • Guohui Lin

    (University of Alberta)

  • Eiji Miyano

    (Kyushu Institute of Technology)

  • Bing Su

    (Xi’an Technological University)

  • Weitian Tong

    (Georgia Southern University)

Abstract

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where $$k = 2$$ k = 2 , including a 17/6-approximation in 2017, a $$(2 + \epsilon )$$ ( 2 + ϵ ) -approximation in 2018, and the most recent polynomial-time approximation scheme in 2020; they all take advantage of the number of stages being two. We deal with an arbitrary constant $$k \ge 3$$ k ≥ 3 , where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We then present how to compute a schedule for each configuration that assigns all the big jobs, followed by how to allocate all the small jobs into the schedule at a cost only a fraction of the makespan. These together lead to a polynomial-time approximation scheme for the problem.

Suggested Citation

  • Mingyang Gong & Guohui Lin & Eiji Miyano & Bing Su & Weitian Tong, 2024. "A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops," Annals of Operations Research, Springer, vol. 335(1), pages 185-204, April.
  • Handle: RePEc:spr:annopr:v:335:y:2024:i:1:d:10.1007_s10479-024-05860-6
    DOI: 10.1007/s10479-024-05860-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-05860-6
    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/s10479-024-05860-6?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. Dong, Jianming & Jin, Ruyan & Luo, Taibo & Tong, Weitian, 2020. "A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops," European Journal of Operational Research, Elsevier, vol. 281(1), pages 16-24.
    2. D. P. Williamson & L. A. Hall & J. A. Hoogeveen & C. A. J. Hurkens & J. K. Lenstra & S. V. Sevast'janov & D. B. Shmoys, 1997. "Short Shop Schedules," Operations Research, INFORMS, vol. 45(2), pages 288-294, April.
    3. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    4. Zhang, Xiandong & van de Velde, Steef, 2012. "Approximation algorithms for the parallel flow shop problem," European Journal of Operational Research, Elsevier, vol. 216(3), pages 544-552.
    5. 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.
    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. Jianming Dong & Ruyan Jin & Jueliang Hu & Guohui Lin, 2019. "A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops," Journal of Combinatorial Optimization, Springer, vol. 37(2), pages 668-684, February.
    2. Jianming Dong & Joshua Chang & Bing Su & Jueliang Hu & Guohui Lin, 2020. "Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments," Journal of Scheduling, Springer, vol. 23(5), pages 595-608, October.
    3. Guangwei Wu & Fu Zuo & Feng Shi & Jianxin Wang, 2024. "On scheduling multiple parallel two-stage flowshops with Johnson’s Rule," Journal of Combinatorial Optimization, Springer, vol. 47(2), pages 1-20, March.
    4. Jansen, Klaus & Mastrolilli, Monaldo & Solis-Oba, Roberto, 2005. "Approximation schemes for job shop scheduling problems with controllable processing times," European Journal of Operational Research, Elsevier, vol. 167(2), pages 297-319, December.
    5. Yong Chen & Yinhui Cai & Longcheng Liu & Guangting Chen & Randy Goebel & Guohui Lin & Bing Su & An Zhang, 2022. "Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph," Journal of Combinatorial Optimization, Springer, vol. 43(3), pages 571-588, April.
    6. Olivier Ploton & Vincent T’kindt, 2023. "Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using Inclusion–Exclusion," Journal of Scheduling, Springer, vol. 26(2), pages 137-145, April.
    7. Shabtay, Dvir & Gerstl, Enrique, 2024. "Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 316(3), pages 887-898.
    8. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    9. D Bai & L Tang, 2010. "New heuristics for flow shop problem to minimize makespan," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(6), pages 1032-1040, June.
    10. Yuri N. Sotskov, 2020. "Mixed Graph Colorings: A Historical Review," Mathematics, MDPI, vol. 8(3), pages 1-24, March.
    11. Nicholas G. Hall & 'Maseka Lesaoana & Chris N. Potts, 2001. "Scheduling with Fixed Delivery Dates," Operations Research, INFORMS, vol. 49(1), pages 134-144, February.
    12. Dvir Shabtay & Baruch Mor, 2024. "Exact algorithms and approximation schemes for proportionate flow shop scheduling with step-deteriorating processing times," Journal of Scheduling, Springer, vol. 27(3), pages 239-256, June.
    13. Kameng Nip & Zhenbo Wang, 2023. "A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints," Journal of Scheduling, Springer, vol. 26(6), pages 543-558, December.
    14. Mehravaran, Yasaman & Logendran, Rasaratnam, 2012. "Non-permutation flowshop scheduling in a supply chain with sequence-dependent setup times," International Journal of Production Economics, Elsevier, vol. 135(2), pages 953-963.
    15. Zhengcai Cao & Lijie Zhou & Biao Hu & Chengran Lin, 2019. "An Adaptive Scheduling Algorithm for Dynamic Jobs for Dealing with the Flexible Job Shop Scheduling Problem," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 61(3), pages 299-309, June.
    16. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    17. 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.
    18. Wang, Ling & Sun, Lin-Yan & Sun, Lin-Hui & Wang, Ji-Bo, 2010. "On three-machine flow shop scheduling with deteriorating jobs," International Journal of Production Economics, Elsevier, vol. 125(1), pages 185-189, May.
    19. Gupta, Jatinder N.D. & Koulamas, Christos & Kyparisis, George J., 2006. "Performance guarantees for flowshop heuristics to minimize makespan," European Journal of Operational Research, Elsevier, vol. 169(3), pages 865-872, March.
    20. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.

    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:annopr:v:335:y:2024:i:1:d:10.1007_s10479-024-05860-6. 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.