Планирование, чтобы минимизировать усеченные пробелы

Question

У меня есть единая работа по длине единицы, набор $ n $ Slots, а также бюджет $ B $ единицы. Если задание запланировано на слоте $ T $ , то он будет потреблять $ C (T) $ бюджета $ b $ . Если задание не запланировано на период $ x $ последовательных слотов, затем штрафной of $ \ lfloor x / 2 \ Rfloor $ возникает. Цель состоит в том, чтобы запланировать работу, чтобы минимизировать сумму наказаний.

Например, для $ n= 12 $ , если задание запланировано на слоте 1, на слоте 3, на слоте 6, а в слоте 12 $ $ , то сумма наказаний составляет $ \ lfloor 1/2 \ Rfloor + \ lfloor 2/2 \ Rfloor + \ lfloor 5 / 2 \ RFLOOR= 0 + 1 + 2= 3 $ .

Эта проблема NP-HARD?

Я пытаюсь уменьшить проблему рюкзака к нему. Преобразование значений в задаче Knaxackack к штрафам каким-то образом трудно, потому что, как только задание запланировано на $ T $ , пенальти инициализируется.

Answer 1

Проблема - это полиномиальное разрешимое время. Чтобы избежать краевых случаев, лучше подумать, что задание необходимо запланировать во время $ 0 $ и что $ C (0 )= 0 $ .

Пусть $ opt [t, p] $ - минимальная сумма бюджета, который должен быть проведен, чтобы запланировать задание в первом $ T $ Слоты с общей наказанием в большей степени $ P $ и с дополнительным ограничением, что задание должно быть запланировано на Время $ t $ .

Пусть $ p (t ', t)=big \ lfloor \ frac {t-t'-1} {2} \ big \ Rfloor $ be Наказание, понесенное, если задание запланировано в Times $ T '$ и $ T> T' $ и не запланирован в любое время между ними.

Тогда $ opt [0, p]= 0 $ и, для $ t> 0 $ : $$ Opt [t, p]= c (t) + \ min _ {\ dounce {t '= 0, \ dots, t-1 \\ p (t', t) \ le p}} opt \ Lep [t ', P - P (T ', T) \ верно] $$

Минимальный достижимый штраф до времени $ T $ , с ограничением, что задание запланировано во время $ T $ , тогда: $$ \ mu (t)=min \ {p \ in \ {1, \ dots, \ lfloor t / 2 \ Rfloor \} \ mid opt [t, p] \ le b \} $$

и минимальный достижимый штраф за вашу проблему: $$ \ min_ {t= 0, \ dots, n} \ левый \ {\ mu (t) + p (t, n + 1) \ right \}. $$

Обратите внимание, что в большинстве $ n \ cdot (p (0, n) +1)= o (n ^ 2) $ значения $ opt [p, t] $ для вычисления.