Back to Search
Start Over
A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops.
- Source :
-
Annals of Operations Research . Apr2024, Vol. 335 Issue 1, p185-204. 20p. - Publication Year :
- 2024
-
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 , 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02545330
- Volume :
- 335
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Annals of Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 176338050
- Full Text :
- https://doi.org/10.1007/s10479-024-05860-6