调度以最小化被截断的间隙

Question

我有一个单位长度的工作，一组 $n$ 插槽和预算 $B$ 单位。如果作业安排在槽位 $t$, ，那么它将消耗 $c(t)$ 预算单位 $B$. 。如果该工作没有安排在一段时间内 $x$ 连续的槽位，然后处罚 $\lfloor x/2 floor$ 发生。目标是安排工作以尽量减少处罚总和。

例如，对于 $n=12$, ，如果作业安排在槽位 1、槽位 3、槽位 6 和槽位 $12$, ，则罚金之和为 $\lfloor 1/2 floor + \lfloor 2/2 floor + \lfloor 5/2 floor = 0+1+2=3$.

这个问题是NP难问题吗？

我正在努力减少背包问题。将背包问题中的值转换为惩罚值在某种程度上是困难的，因为一旦工作安排在 $t$, ，惩罚被初始化。

Answer 1

该问题是多项式时间可解的。为了避免极端情况，最好认为该作业需要按时间安排 $0$ 然后 $c(0)=0$.

让 $OPT[t,p]$ 是为了在第一时间安排工作而需要花费的最低预算金额 $t$ 总惩罚最多为 $p$ 并且还有一个额外的限制，即必须按时安排作业 $t$.

让 $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big floor$ 如果工作有时被安排，则会受到处罚 $t'$ 和 $t > t'$ 并且中间的任何时间都没有安排。

然后 $OPT[0,p] = 0$ 并且，对于 $t>0$: $$ opt [t，p] = c（t） + min _ { oretack {t'= 0， dots，t-1 p（t'，t'，t） le p}}} opt left [t '，p -p（t'，t） right] $$

迄今为止可达到的最低处罚 $t$, ，约束作业在时间安排 $t$, ，则：$$ mu（t）= min {p in {1， dots， lfloor t/2 rfloor } mid opt [t，p] le b } $

您的问题可达到的最低惩罚是：$$ min_ {t = 0， dots，n} left { mu（t） + p（t，n + 1） right }。$$

注意最多有 $n \cdot (P(0,n)+1) = O(n^2)$ 价值观 $OPT[p,t]$ 计算。