On scheduling an unbounded batch machine
On scheduling an unbounded batch machine
复制标题
DOI：
10.1016/s0167-6377(02)00186-4
复制
发表时间：
2003-01-01
影响因子：
1.1
通讯作者：
Cheng, TCE
中科院分区：
文献类型：
--
作者：
Liu, ZH;Yuan, JJ;Cheng, TCE
批处理机是指一批最多可以同时处理c个作业的机器，该批的处理时间等于分配给它的作业的最长处理时间。本文讨论了无界批处理机调度问题的复杂性，即c=+无穷大。我们证明了最小化总拖期是二进制NP难问题，这在文献中一直是一个公开的问题。此外，我们还证明了具有任意正则目标的无界分批机器排序问题的伪多项式可解性。这不同于有界批处理机和经典的单机调度问题，它们中的大多数具有不同的交货日期，都是一元NP难问题。结合已有的结果，本文给出了无界批处理机调度复杂性的一个几乎完全的映射。(C)2002 Elsevier Science B.V.保留所有权利。
A batch machine is a machine that can process up to c jobs simultaneously as a batch, and the processing time of the batch is equal to the longest processing time of the jobs assigned to it. In this paper, we deal with the complexity of scheduling an unbounded batch machine, i.e., c = +infinity. We prove that minimizing total tardiness is binary NP-hard, which has been an open problem in the literature. Also, we establish the pseudopolynomial solvability of the unbounded batch machine scheduling problem with job release dates and any regular objective. This is distinct from the bounded batch machine and the classical single machine scheduling problems, most of which with different release dates are unary NP-hard. Combined with the existing results, this paper provides a nearly complete mapping of the complexity of scheduling an unbounded batch machine. (C) 2002 Elsevier Science B.V. All rights reserved.