@inproceedings{f25c416112d24bbb83ef68d8b75a1226,
title = "A PTAS for the multiple parallel identical multi-stage flow-shops to minimize the makespan",
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.",
keywords = "Flow-shop scheduling, Linear program, Makespan, Multiprocessor scheduling, Polynomial-time approximation scheme",
author = "Weitian Tong and Eiji Miyano and Randy Goebel and Guohui Lin",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 10th International Workshop on Frontiers in Algorithmics, FAW 2016 ; Conference date: 30-06-2016 Through 02-07-2016",
year = "2016",
doi = "10.1007/978-3-319-39817-4\_22",
language = "English",
isbn = "9783319398167",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "227--237",
editor = "Sergey Bereg and Daming Zhu",
booktitle = "Frontiers in Algorithmics - 10th International Workshop, FAW 2016, Proceedings",
address = "Germany",
}