Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time
Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time
复制标题
具有公共批量大小以最小化总加权完成时间的单机串行批处理调度问题
DOI：
10.1016/j.ijpe.2004.04.014
复制
发表时间：
2007-02
影响因子：
12
通讯作者：
Cheng, T. C. E.
中科院分区：
文献类型：
--
作者：
Yuan, J. J.;Ng, C. T.;Lin, Y. X.;Cheng, T. C. E.
在本文中，我们考虑单机串行批处理调度问题，以最小化总加权完成时间，并限制每个批次恰好包含 k 个作业。我们证明，即使批量大小为 3 并且每个作业的权重等于其处理时间，这个问题也是强 NP 困难的。对于以下两种特殊情况，我们还给出了 O(nlogn) 时间算法： (1) 作业是逆向一致的，即 pi<pjimplies wi⩾wj； (2) 批量大小为 2，作业的权重与其处理时间成正比，即，对于常数 α>0，wj=αpj。
In this paper we consider the single machine serial-batching scheduling problem to minimize total weighted completion time with the restriction that each batch contains exactly k jobs. We show that this problem is strongly NP-hard even when the batch size is 3 and the weight of each job is equal to its processing time. We also give O(nlogn) time algorithms for the following two special cases: (1) the jobs are inversely agreeable, i.e., pi<pjimplies wi⩾wj; (2) the batch size is 2 and the weights of the jobs are proportional to their processing times, i.e., wj=αpjfor a constant α>0.
登录
查看更多内容
影响因子：
6.4
作者：
Potts, CN;Kovalyov, MY
通讯作者：
Kovalyov, MY
DOI：
10.1016/0166-218x(93)90160-p
发表时间：
1993-09
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Suh-Ryung Kim;T. McKee;F. McMorris;F. Roberts
通讯作者：
Suh-Ryung Kim;T. McKee;F. McMorris;F. Roberts
DOI：
10.1201/9781420049503-c36
发表时间：
2004-12
期刊：
Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture
影响因子：
--
作者：
David R Karger;C. Stein;J. Wein
通讯作者：
David R Karger;C. Stein;J. Wein
影响因子：
1.2
作者：
P. Baptiste
通讯作者：
P. Baptiste
影响因子：
--
作者：
T. Cheng;M. Kovalyov
通讯作者：
T. Cheng;M. Kovalyov