具有阶梯成本的约束调度的NP硬度证明

Question

我正在处理一个看起来像赋值问题变体的问题。有些任务需要分配给服务器。服务器的成本总和需要最小化。以下条件成立：

1. 每个任务都有一个单元大小

2. 一个任务不能在多个服务器之间分配。一个任务必须由一台服务器来处理。

3. 服务器对可分配给它的最大任务数有限制。

4. 任务分配的成本函数是一个阶梯函数。服务器的成本最低为"A"。对于服务器处理的每项任务，成本都会增加1。如果分配给特定服务器的任务数超过其容量的一半，则该服务器的成本将跃升，等于正数"d"。

   4. 任务具有偏好，即给定的任务可以分配给少数服务器中的一个

我有一种感觉，这是一个NP难问题，但我似乎找不到一个NP完全问题来映射它。我尝试过装箱、分配问题、多背包、二分图匹配，但这些问题都不具备我问题的所有关键特征。你能提出一些与之对应的问题吗？

感谢

Saqib

Answer 1

您是否尝试过将集合分区问题简化为您的问题？

SET-PART（代表"集合划分"）决策问题询问是否存在将给定的数字集合S划分为两个集合S1和S2，使得S1中的元素之和等于S2中的元素的和。这个问题是NP完全的。

您的问题似乎与m-PROCESSOR决策问题有关。给定处理时间为t1,t2,...,tn的n>0任务{a1,a2,...,an}的非空集合A，m-PROCESSOR问题询问您是否可以在m等处理器之间调度任务，以便所有任务最多在k>0时间步长内完成。（处理时间是（正）自然数。）

将SET-PART还原为m-PROCESSOR是非常容易的：首先证明了具有m=2的特殊情况是NP完全的；则使用此来表明CCD_ 18对于所有CCD_。（斯洛文尼亚语的减少。）

希望这能有所帮助。

第1版：哎呀，这个m-PROCESSOR的问题似乎非常类似于分配问题。