@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",

}