A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
A PTAS for the Multiple Parallel Identical Multi-stage Flow-Shops to Minimize the Makespan
复制标题
DOI：
10.1007/978-3-319-39817-4_22
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Weitian Tong;Eiji Miyano;R. Goebel;Guohui Lin
中科院分区：
文献类型：
--
作者：
Weitian Tong;Eiji Miyano;R. Goebel;Guohui Lin
在并行k阶段流水作业问题中，我们给出了中间阶段流水作业和一组作业。每个作业可以由任何一个流水作业处理，但不允许在流水作业之间切换。目标是最小化最大完工时间，也就是最后一个工件的完工时间。该问题推广了经典的并行同机排序问题和经典的流水车间排序问题，因而是一个困难问题。当k是固定常数时，我们提出了一个多项式时间近似方案。其关键技术是对大工件进行遍历，对小工件进行线性规划，最后将小数小工件相加。这种技术已被用于类似的近似方案的设计。
In theparallelk-stage flow-shopsproblem, we are givenmidenticalk-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) and the classical flow-shop scheduling (where) problems, and thus it is-hard. We present a polynomial-time approximation scheme for the problem, whenmandkare fixed constants. The key technique is to enumerate over schedules forbigjobs, solve a linear programming forsmalljobs, and add the fractional small jobs at the end. Such a technique has been used in the design of similar approximation schemes.