Minimizing the Total Late Work on an Unbounded Batch Machine

摘要：

We consider the problem of minimizing the total late work (nΣj=1 Vj) on an unbounded batch processing machine, where Vj = minTj, pj and Tj = maxCj dj, 0. The batch processing machine can process up to B (B ≥ n) jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time, respectively. For a batch of jobs,the processing time of the batch is equal to the largest processing time among the jobs in this batch.In this paper, we prove that the problem 1|B ≥ n|nΣj=1 Vj is NP-hard.

关键词： Scheduling Batching machine Late work NP-hardness

作者: Jianfeng Ren Yuzhong Zhang Sunguo

作者单位: College of Operations Research and Management Sciences, Qufu Normal University, Shangdong, 276826, C Department of Mathematics, Qufu Normal University, Shangdong, 276826, China

会议类型: 国际会议

会议名称: The Seventh International Symposium(ISORA08)(第七届国际效力研究及其应用学术会议)

会议地点: 云南丽江

会议语种:英文

页码: 74-81

在线出版日期: 2008-10-31（万方平台首次上网日期，不代表论文的发表时间）