Advertisement
Published in:
2016 | OriginalPaper | Chapter
A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
Authors : Weitian Tong, Eiji Miyano, Randy Goebel, Guohui Lin
Published in: Frontiers in Algorithmics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 \(\text {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.