A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops
复制标题
并行相同两阶段开放车间调度的完全多项式时间近似方案
DOI：
10.1007/s10878-018-0314-6
复制
发表时间：
2018-06
影响因子：
1
通讯作者：
Guohui Lin
中科院分区：
文献类型：
--
作者：
Jianming Dong;Ruyan Jin;Jueliang Hu;Guohui Lin
两级OpenShop由第一级中的一台机器和第二级中的一台机器组成；在两级OpenShop上处理的作业意味着它由两台机器中的每台机器以任何顺序非抢占式地处理。我们考虑了有多个平行的完全相同的两阶段开放车间可用时的排序问题，目标是最小化完工时间。通过揭示关键作业在两阶段OpenShop最优调度中的重要作用，提出了按新的关键作业顺序对作业进行排序，并以此为基础设计了一个伪多项式时间动态规划精确算法来求解任意固定数量的两阶段Open Shop调度问题。然后，使用标准的标度技术，我们将动态规划算法发展成一个完全多项式时间近似方案。这些结果改进了以前提出的恒比逼近算法。
A two-stage openshop consists of a machine in the first stage and a machine in the second stage; a job processed on the two-stage openshop means it is processed non-preemptively by each of the two machines, in whichever order. We consider the scheduling problem at the availability of multiple parallel identical two-stage openshops, with the goal to minimize the makespan. By uncovering the important role of thecriticaljob in the optimal schedule on a two-stage openshop, we propose to sort the jobs in the novelcritical-job order, and use this order to design a pseudo-polynomial time dynamic programming exact algorithm to solve our scheduling problem with any fixed number of two-stage openshops. Afterwards, using the standard scaling technique, we develop the dynamic programming algorithm into a fully polynomial-time approximation scheme. These results improve previously proposed constant ratio approximation algorithms.
登录
查看更多内容
DOI：
10.1007/978-0-387-39940-9_3525
发表时间：
2018-09
期刊：
2006 15th IEEE International Conference on High Performance Distributed Computing
影响因子：
--
作者：
Susmita Bandyopadhyay
通讯作者：
Susmita Bandyopadhyay
影响因子：
6.4
作者：
Zhang, Xi;ong;van de Velde, Steef
通讯作者：
van de Velde, Steef
DOI：
10.1016/s0167-6377(99)00005-x
发表时间：
1999-05
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
P. Schuurman;G. Woeginger
通讯作者：
P. Schuurman;G. Woeginger
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
DOI：
10.1007/978-1-4613-0303-9_25
发表时间：
1998
期刊：
--
影响因子：
--
作者：
Bo Chen;C. Potts;G. Woeginger
通讯作者：
Bo Chen;C. Potts;G. Woeginger