Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time
Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time
复制标题
在相同机器上进行抢先调度并进行交付协调，以最大程度地缩短最大交付完成时间
DOI：
10.1016/j.tcs.2015.03.046
复制
发表时间：
2015-06
影响因子：
1.1
通讯作者：
Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Youjun Chen;Lingfa Lu;Jinjiang Yuan
在本文中，我们考虑一个两阶段的调度问题，在相同的机器中的工作是第一次加工的m个相同的机器在制造设施，然后交付给他们的客户在一个车辆，可以提供一个工件在每次装运。目标是最小化最大交付完成时间，即所有作业交付给各自的客户和车辆返回设施的时间。我们首先证明了这个问题是强NP-困难的。然后，我们提出了一个3 - 2近似算法，并表明该界是紧的。
In this paper, we consider a two-stage scheduling problem on identical machines in which the jobs are first processed preemptively on m identical machines at a manufacturing facility and then delivered to their customers by one vehicle which can deliver one job at each shipment. The objective is to minimize the maximum delivery completion time, ie, the time when all the jobs are delivered to their respective customers and the vehicle returns to the facility. We first show that the problem is strongly NP-hard. We then present a 3 2-approximation algorithm and show that the bound is tight.
登录
查看更多内容
具有作业交付协调的机器调度问题
影响因子：
6.4
作者：
Dosa, Gyorgy;Zhong, Weiya;Tan, Zhiyi
通讯作者：
Tan, Zhiyi
DOI：
10.1016/j.tcs.2006.04.014
发表时间：
2005-06
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Yong He;Weiya Zhong;Huikun Gu
通讯作者：
Yong He;Weiya Zhong;Huikun Gu
DOI：
10.1287/moor.17.1.22
发表时间：
1992-02
期刊：
Math. Oper. Res.
影响因子：
--
作者：
Leslie A. Hall;D. Shmoys
通讯作者：
Leslie A. Hall;D. Shmoys
DOI：
10.1016/j.ejor.2003.03.002
发表时间：
2005-02
期刊：
Eur. J. Oper. Res.
影响因子：
--
作者：
A. Soukhal;A. Oulamara;P. Martineau
通讯作者：
A. Soukhal;A. Oulamara;P. Martineau
影响因子：
2
作者：
Chung-Yee Lee;Zhi-Long Chen
通讯作者：
Chung-Yee Lee;Zhi-Long Chen