Single machine scheduling with job delivery to multiple customers
Single machine scheduling with job delivery to multiple customers
复制标题
单机调度，向多个客户交付作业
DOI：
10.1007/s10951-017-0508-2
复制
发表时间：
2018-06
影响因子：
2
通讯作者：
Guohui Lin
中科院分区：
文献类型：
--
作者：
Jianming Dong;Xueshi Wang;Jueliang Hu;Guohui Lin
我们研究向多个客户交付作业的单机调度问题。在这个问题中，每个作业都需要在一台机器上处理，然后由一辆车交付给客户，其中作业的物理尺寸代表它在车辆上占用的空间比例。车辆将货物从机器交付给客户，然后必须返回机器以交付下一批货物。机器和不同客户之间的往返需要不同的常数时间。目标是最大限度地缩短完工时间，届时所有作业均已处理完毕并交付给各自的客户，然后车辆返回机器。我们针对一般情况提出了一种 2 近似算法；当只有两个客户时，我们提出了改进的 5/3 近似算法。这两种算法的设计和性能分析综合了单机调度问题、装箱问题和背包问题的几种已知结果和技术。
We investigate a single machine scheduling problem with job delivery to multiple customers. In this problem, each job needs to be processed on the single machine, and then delivered by a single vehicle to its customer, where the job has a physical size representing the fraction of space it occupies on the vehicle. The vehicle delivers a shipment from the machine to a customer and has to return back to the machine for delivering the next shipment. It takes different constant time for the round trips between the machine and the different customers. The goal is to minimize the makespan, by that time all the jobs are processed and delivered to their respective customers, and the vehicle returns back to the machine. We propose a 2-approximation algorithm for the general case; when there are only two customers, we present an improved 5/3-approximation algorithm. The design and performance analysis of these two algorithms integrate several known results and techniques for the single machine scheduling problem, the bin-packing problem, and the knapsack problem.
登录
查看更多内容
具有作业交付协调的机器调度问题
影响因子：
6.4
作者：
Dosa, Gyorgy;Zhong, Weiya;Tan, Zhiyi
通讯作者：
Tan, Zhiyi
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
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
影响因子：
2.3
作者：
F. Hulting;Jeffrey A. Robinson
通讯作者：
F. Hulting;Jeffrey A. Robinson
DOI：
10.1016/0196-6774(84)90032-4
发表时间：
1982
期刊：
J. Algorithms
影响因子：
--
作者：
David S. Johnson
通讯作者：
David S. Johnson