带阶梯成本约束调度的NP-硬度证明

Question

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

1. 每个任务都有一个单位大小。
2. 一个任务不能在多个服务器之间分配。任务必须由一台服务器来处理。
3. 服务器对分配给它的最大任务数有限制。
4. 任务分配的成本函数是一个阶梯函数。服务器需要最小的成本a。对于服务器处理的每一项任务，成本增加1。如果分配给特定服务器的任务数量超过其容量的一半，则该服务器的成本会跳升，等于正数“d”。

1. Tasks have preferences, i.e., a given task may be assigned to one of a few of the servers.

​

我有一种感觉，这是一个NP难题，但我似乎找不到一个NP完全问题来映射到它。我尝试过Bin打包，赋值问题，多背包，二部图匹配，但这些问题都没有我的问题的所有关键特征。你能提出一些问题吗？

感谢并致以最良好的问候

萨齐布

Answer 1

你试过把集划分问题缩小到你的吗？

SET-PART (表示“集合分区”)决策问题询问给定的集合S是否有一个划分为S1和S2，因此S1中的元素之和等于S2中的元素之和。这个问题众所周知是NP-完全的.

您的问题似乎与m-PROCESSOR决策问题有关。给定具有处理时间为A的非空n>0任务{a1,a2,...,an}，m-PROCESSOR问题询问是否可以在m相等处理器之间安排任务，以便所有任务在最多k>0时间步骤中完成。(处理时间为(正数)自然数。)

将SET-PART简化为m-PROCESSOR很容易:首先证明特殊情况( m=2 )是NP-完全的；然后用这个表示m-PROCESSOR对于所有m>=2都是NP-完全的。(A 斯洛文尼亚文减少e.)

希望这能有所帮助。

编辑1:哎呀，这个m-PROCESSOR看起来非常类似于赋值问题。