A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
Full Text: Tong2016_Chapter_APTASForTheMultipleParallelIde.pdf
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 𝑘=1 ) and the classical flow-shop scheduling (where 𝑚=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.
Citation
W. Tong, E. Miyano, R. Goebel, G. Lin. "A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan". International Frontiers of Algorithmics Workshop, pp 227-237, June 2016.| Keywords: | Multiprocessor scheduling, Flow-shop scheduling, Makespan, Linear program, Polynomial-time approximation scheme |
| Category: | In Workshop |
| Web Links: | Springer |
BibTeX
@misc{Tong+al:(FAW)16,
author = {Weitian Tong and Eiji Miyano and Randy Goebel and Guohui Lin},
title = {A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to
Minimize the Makespan},
Pages = {227-237},
booktitle = {International Frontiers of Algorithmics Workshop},
year = 2016,
}Last Updated: June 09, 2020Submitted by Sabina P
