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

Mingyang Gong (), Guohui Lin (), Eiji Miyano (), Bing Su () and Weitian Tong ()
Additional contact information
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

Annals of Operations Research, 2024, vol. 335, issue 1, No 8, 185-204

Abstract: 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.

Keywords: Scheduling; Parallel identical multi-stage flow-shops; Makespan; Configuration; Polynomial-time approximation scheme (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-024-05860-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:335:y:2024:i:1:d:10.1007_s10479-024-05860-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-024-05860-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().