TY - JOUR
T1 - A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops
AU - Gong, Mingyang
AU - Lin, Guohui
AU - Miyano, Eiji
AU - Su, Bing
AU - Tong, Weitian
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.
PY - 2024/4
Y1 - 2024/4
N2 - 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, including a 17/6-approximation in 2017, a (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≥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.
AB - 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, including a 17/6-approximation in 2017, a (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≥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.
KW - Configuration
KW - Makespan
KW - Parallel identical multi-stage flow-shops
KW - Polynomial-time approximation scheme
KW - Scheduling
UR - http://www.scopus.com/inward/record.url?scp=85185266761&partnerID=8YFLogxK
U2 - 10.1007/s10479-024-05860-6
DO - 10.1007/s10479-024-05860-6
M3 - Article
AN - SCOPUS:85185266761
SN - 0254-5330
VL - 335
SP - 185
EP - 204
JO - Annals of Operations Research
JF - Annals of Operations Research
IS - 1
ER -