Pianificazione per minimizzare gli spazi troncati

Question

Ho un singolo lavoro di lunghezza unitario, un set di $ N $ slot e un budget di $ B $ unità. Se il lavoro è programmato su slot $ T $ , quindi consumerà $ c (t) $ unità del bilancio $ B $ . Se il lavoro non è programmato per un periodo di $ x $ slot consecutivi, quindi una penalità di $ \ lfloor x / 2 \ rfloor $ si verifica. L'obiettivo è pianificare il lavoro al fine di minimizzare la somma delle sanzioni.

Ad esempio, per $ n= 12 $ , se il lavoro è pianificato su slot 1, allo slot 3, allo slot 6, e allo slot $ 12 $ , quindi la somma delle sanzioni è $ \ lfloor 1/2 \ rfloor + \ lfloor 2/2 \ rfloor + \ lfloor 5 / 2 \ rfloor= 0 + 1 + 2= 3 $ .

È questo problema NP-HARD?

Sto cercando di ridurre il problema dello zaino. Trasformare i valori nel problema dello zaino alle sanzioni è in qualche modo difficile, perché una volta che il lavoro è programmato a $ T $ , la penalità è inizializzata.

Answer 1

Il problema è solvibile polinomiale. Per evitare casi di bordo è meglio pensare che il lavoro debba essere programmato al momento $ 0 $ e quella $ c (0 )= 0 $ .

Let $ opt [t, p] $ essere l'importo minimo di budget che deve essere speso per pianificare il lavoro nella prima classe $ T $ slot con una pena complessiva di al massimo $ p $ e con il vincolo aggiuntivo che il lavoro deve essere programmato a tempo $ T $ .

Let $ p (t ', t)=big \ lfloor \ frac {t-t'-1} {2} \ big \ rfloor $ La penalità sostenuta se il lavoro è pianificato a volte $ t '$ e $ t> t' e non è programmato in qualsiasi momento intermedio.

quindi $ opt [0, p]= 0 $ e, per $ T> 0 $ : $$ Opt [t, p]= c (t) + \ min _ {\ Subtack {T '= 0, \ Dots, T-1 \\ P (T', t) \ le p}} opt \ left [t ', P - P (T ', T) \ destra] $$

La sanzione minima raggiungibile fino a tempo $ T $ , con il vincolo che il lavoro è programmato al momento $ t $ , è quindi: $$ \ mu (t)=min \ {p \ in \ {1, \ dots, \ lfloor t / 2 \ rfloor \} \ medio opt [t, p] \ le b \} $$

E la penalità minima raggiungibile per il tuo problema è: $$ \ min_ {T= 0, \ Dots, n} \ Sinistra \ {\ MU (T) + P (T, N + 1) \ Destra \}. $$

Si noti che ci sono al massimo $ n \ cdot (p (0, n) +1)= o (n ^ 2) $ valori $ opt [p, t] $ per calcolare.