Scheduling Equal Processing Time Jobs to Minimize the Weighted Number of Late Jobs
Scheduling Equal Processing Time Jobs to Minimize the Weighted Number of Late Jobs
复制标题
安排相等处理时间的作业以最小化迟到作业的加权数量
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Svetlana A. Kravchenko
中科院分区：
文献类型：
--
作者：
P. Brucker;Svetlana A. Kravchenko
我们证明问题 P ∣ pi = p, pmtn ∣ ΣwiUi 是一元 NP 困难问题，尽管相应的非抢占问题可以在 O(n log n) 时间内解决，其中 n 是作业数量。这与以下事实形成鲜明对比：通常先发制人的问题并不比非先发制人的问题更难。
We prove that the problem P ∣ pi = p, pmtn ∣ ∑wiUi is unary NP-hard although the corresponding nonpreemptive problem can be solved in O(n log n) time, where n is the number of jobs. This contrasts the fact that usually preemptive problems are not harder than their nonpreemptive counterparts.