任务调度中的NP完全性

Question

因此,这是一个引人深思的问题,可以让我的教授了解NP-Completeness的概念.我知道为什么应该有一个解决方案,由于NP-Completeness的规则,但我不知道如何找到它.所以这是问题所在:

问题是两个处理器的简单任务调度问题.每个处理器可以处理其中一个n任务,任何两个任务都可以同时完成.每个任务都有一个结束时间e,必须在此时完成.每个任务也有一个持续时间d.所有时间值,例如结束时间,持续时间和系统中的当前时间(时间将从0开始)都是整数.因此我们给出了一个n任务列表,我们需要使用这两个处理器来安排它们.如果无法安排任何一个,则算法必须不返回任何解决方案.请记住,顺序无关紧要,只要没有重叠并且每个任务在截止日期之前完成,哪个处理器获取哪个任务都无关紧要.

所以这里是问题得到概念/抽象的地方,比如我们可以访问一个特殊的小函数,我们不知道它是如何工作的,我们所知道的就是:给定一个n任务列表和当前的时间表,它将返回true或false基于从这一点来看,算法是否可以解决.此函数假定已安排的任务是一成不变的,它只会更改未安排的任务的时间.但是,所有这个函数都返回true或false,如果找到解决方案,它将不会给你正确的时间表.关键是你可以在执行调度问题时使用特殊功能.目标是解决调度问题,并使用对特殊函数的多项式调用次数,返回正确调度的每个作业的工作时间表.

编辑:澄清一下,问题是:创建一个解决方案来安排所有n任务,没有任何超过截止日期,使用多项式调用"特殊功能".

我认为这个问题是为了证明验证解是多项式,但发现它是非多项式的.但是我的教授坚持认为有一种方法可以使用对特殊函数的多项式调用来解决这个问题.由于整个问题是NP-Complete,这将证明运算符的非多项式方面在算法的"决策部分"中出现.

如果你希望我清理任何东西只是发表评论,我知道这不是对这个问题的完美解释.

Answer 1

给定一个返回或仅M返回的预言机：truefalse

输入：任务 - 任务列表 输出：时间表：每个任务算法的三元组（任务、处理器、启动）：

While there is some unscheduled task:
   let p be the processor that currently finished up his scheduled tasks first
   let x be the first available time on x
   for each unscheduled task t:
      assign t with the triplet: (t,p,x)
      run M on current tasks
      if M answers true:
            break the for loop, continue to next iteration of while loop
      else:
            unassign t, and continue to next iteration of for loop
    if no triplet was assigned, return NO_SOLUTION
return all assigned triplets

• 上面的运行在多项式时间内 - 它需要O(N^2)调用M.
• 上述算法的正确性可以通过归纳法来证明，其中归纳假设是在k循环完一轮之后，如果在它之前有一个解，那么在它之后（并且在分配某个任务之后）仍然有一个解。证明了这一主张后，算法的正确性就很容易实现了k=#tasks

正式证明上述主张：

• 当 k=0 时，归纳基础是微不足道的。
• 假设：对于任何 k < i，“如果在第 k 轮之前有解决方案，则在第 k 轮之后仍然有一个解决方案”的说法是正确的
• 证明：

假设有一些解{ (tj,pj,xj) | j=1,...,n}，按 排序j<u <-> xj<xu，并且还假设 t1,t2,...,ti-1 的分配与算法产生的相同（归纳假设）。现在，我们要分配ti，并且我们将能够做到这一点，因为我们将找到最小的可用时间戳 ( xi)，并在其上放置一些任务。我们将找到一些任务，因为这ti是一种可能性 - 它不会“失败”并产生“NO_SOLUTION”。
另外，由于该算法在迭代中不会产生“NO_SOLUTION” i，因此从 的正确性来看M，它将产生一些任务t，通过分配(t,p,x)- 仍然会有一个解决方案，并且步骤的要求i得到证明。