Abstract
In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k = 1) and the classical flow-shop scheduling (where m = 1) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme for the problem, when m and k are fixed constants. The key technique is to enumerate over schedules for big jobs, solve a linear programming for small jobs, and add the fractional small jobs at the end. Such a technique has been used in the design of similar approximation schemes.
Original language | English |
---|---|
Title of host publication | Frontiers in Algorithmics - 10th International Workshop, FAW 2016, Proceedings |
Editors | Sergey Bereg, Daming Zhu |
Publisher | Springer Verlag |
Pages | 227-237 |
Number of pages | 11 |
ISBN (Print) | 9783319398167 |
DOIs | |
State | Published - 2016 |
Event | International Workshop on Frontiers in Algorithmics - Qingdao, China Duration: Jun 30 2016 → Jul 2 2016 Conference number: 10 https://link.springer.com/book/10.1007/978-3-319-39817-4 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 9711 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Workshop on Frontiers in Algorithmics |
---|---|
Abbreviated title | FAW |
Country/Territory | China |
City | Qingdao |
Period | 06/30/16 → 07/2/16 |
Internet address |
Scopus Subject Areas
- Theoretical Computer Science
- General Computer Science
Keywords
- Flow-shop scheduling
- Linear program
- Makespan
- Multiprocessor scheduling
- Polynomial-time approximation scheme