首页> 外文OA文献 >Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time
【2h】

Single machine serial-batching scheduling problem with a common batch size to minimize total weighted completion time

机译:具有通用批处理大小的单机串行批处理调度问题,以最大程度减少总加权完成时间

摘要

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 (n log n) time algorithms for the following two special cases: (1) the jobs are inversely agreeable, i.e., pi pj implies wi ≥ wj; (2) the batch size is 2 and the weights of the jobs are proportional to their processing times, i.e., wj = α pj for a constant α 0.
机译:在本文中,我们考虑了单机串行批处理调度问题,以在限制每个批处理恰好包含k个作业的情况下最大程度地减少总加权完成时间。我们表明,即使批量大小为3并且每个作业的权重等于其处理时间,此问题也对NP至关重要。对于以下两种特殊情况,我们还给出了O(n log n)时间算法:(1)作业是逆向一致的,即pi j意味着wi≥wj; (2)批量大小为2,并且作业的权重与它们的处理时间成正比,即对于常数α> 0,wj =αpj。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号