切り捨てられた隙間を最小にするためのスケジューリング

Question

単位長さのジョブ、 $ n $ スロット、および $ bの予算$ 単位。ジョブがSlot $ T $ でスケジュールされている場合、それは $ c（t）$ 単位を消費します予算 $ b $ 。ジョブが $ x $ 連続スロットの間にスケジュールされていない場合、 $ \ lfloor x / 2のペナルティ\ rfroor $ が発生します。目的は、ペナルティの合計を最小限に抑えるためにジョブをスケジュールすることです。

たとえば、 $ n= 12 $ の場合、ジョブがスロット1でスロット1、スロット3、スロット6、およびスロット $ 12 $ 、ペナルティの合計は $ \ lfloor 1/2 \ rfrooor + \ lfloor 2/2 \ rfloor + \ lfor 5です。 / 2 \ rfloor= 0 + 1 + 2= 3 $ 。

この問題はNP-HARD？

ナップザック問題をそれに縮小しようとしています。ジョブが $ t $ でスケジュールされると、ペナルティが初期化されるため、CanapSackの問題の値をペナルティに変換することはどういうわけか難しいです。

Answer 1

問題は多項式解除可能です。 エッジケースを避けるためには、ジョブは時刻 $ 0 $ 、その $ c（0）でスケジュールする必要があると考えることが良いことです。 ）= 0 $ 。

let $ OPT [T、P] $ 最初の $ t $ スロットは、ほとんどの $ p $ の全体的なペナルティと、そのジョブをスケジュールする必要があるという追加の制約があります。 time $ t $ 。

$ p（t '、t）=big \ lfloor \ frac {t-t'-1} {2} \ big \ rfrooor $ ジョブが時々スケジュールされている場合、 $ t '$ 、および $ t> t' $ $ で発生したペナルティ間にいつでもスケジュールされていません。

その後 $ opt [0、p]= 0 $ 、および $ t> 0 $ ： $$ opt [t、p]= c（t）+ \ min _ {\ sustack {t '= 0、\ dots、t-1 \\ p（t'、t）\ le p}} opt \ left [t '、 P - P（T '、T）\ right] $$

最小値 $ t $ まで、ジョブが時刻 $ tでスケジュールされているという制約があります。 $ は次のとおりです。 $$ \ mu（t）=min \ {p \ in \ {1、\ dots、\ lfort、\ lforor t / 2 \ rfloor \} \ mid opt [t、p] \}} $$

とあなたの問題に対する達成可能な最小ペナルティは次のとおりです。 $$ \ 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] $ を計算します。