2

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

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

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

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

  4. 任务分配的成本函数是一个阶梯函数。服务器产生最低成本“a”。对于服务器处理的每个任务，成本增加 1。如果分配给特定服务器的任务数量超过其容量的一半，则该服务器的成本会增加一个正数“d”。

    1. 任务具有偏好，即，可以将给定任务分配给几个服务器之一。

我有一种感觉，这是一个 NP-Hard 问题，但我似乎无法找到一个 NP-Complete 问题来映射到它。我试过装箱、分配问题、多个背包、二分图匹配，但这些问题都没有我的问题的所有关键特征。你能提出一些映射到它的问题吗？

谢谢和最好的问候

萨奇布

4

1 回答 1

0

您是否尝试过将设置分区问题减少到您的问题？

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

您的问题似乎与m-PROCESSOR决策问题有关。给定一组具有处理时间A的非空n>0任务，问题询问您是否可以在相等的处理器之间安排任务，以便所有任务在大多数时间步内完成。（处理时间是（正）自然数。）{a1,a2,...,an}t1,t2,...,tnm-PROCESSORmk>0

SET-PARTto的归约m-PROCESSOR非常简单：首先证明特殊情况 withm=2是 NP 完全的；然后用它来证明m-PROCESSOR对 all 是 NP 完全的m>=2。（斯洛文尼亚语的减少。）

希望这可以帮助。

编辑1：哎呀，这个m-PROCESSOR东西似乎与分配问题非常相似。

于 2014-09-15T10:55:38.143 回答