A note on the complexity of the problem of two-agent scheduling on a single machine
A note on the complexity of the problem of two-agent scheduling on a single machine
复制标题
DOI：
10.1007/s10878-006-9001-0
复制
发表时间：
2006-12-01
影响因子：
1
通讯作者：
Yuan, J. J.
中科院分区：
文献类型：
--
作者：
Ng, C. T.;Cheng, T. C. E.;Yuan, J. J.
我们考虑一台机器上的双智能体调度问题，其目标是最小化第一个智能体的总完成时间，同时限制第二个智能体的延迟作业数量不能超过给定数量。据文献报道，这个问题的复杂性仍然是开放的。本文证明了该问题在高多重编码下是np困难的，在二进制编码下可以在伪多项式时间内解决。当第一个智能体的目标是最小化总加权完成时间时，我们证明了这个问题是强np困难的，即使第二个智能体的延迟作业数量被限制为零。
We consider a two-agent scheduling problem on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the number of tardy jobs of the second agent cannot exceed a given number. It is reported in the literature that the complexity of this problem is still open. We show in this paper that this problem is NP-hard under high multiplicity encoding and can be solved in pseudo-polynomial time under binary encoding. When the first agent's objective is to minimize the total weighted completion time, we show that the problem is strongly NP-hard even when the number of tardy jobs of the second agent is restricted to be zero.