Agendamento para minimizar as lacunas truncadas

Question

Eu tenho um único trabalho de comprimento da unidade, um conjunto de $ n $ slots e um orçamento de $ B $ unidades. Se o trabalho estiver programado no slot $ t $ , então ele consome $ c (t) $ unidades do orçamento $ B $ . Se o trabalho não estiver programado por um período de $ x $ slots consecutivos, então uma penalidade de $ \ lFlloor x / 2 \ rfloor $ ocorre. O objetivo é agendar o trabalho, a fim de minimizar a soma das penalidades.

Por exemplo, para $ n= 12 $ , se o trabalho for agendado no slot 1, no slot 3, no slot 6, e no slot $ 12 $ , então a soma das penalidades é $ \ lFlloor 1/2 \ rFloor + \ lFloor 2/2 \ rFloor + \ lFloor 5 / 2 \ rfloor= 0 + 1 + 2= 3 $ .

é este problema np-hard?

Eu estou tentando reduzir o problema da mochila para ele. Transformar os valores no problema da mochila para as penalidades é de alguma forma difícil, porque uma vez que o trabalho é agendado para $ t $ , a penalidade é inicializada.

Answer 1

O problema é o tempo polinomial solublível. Para evitar casos de borda, é melhor pensar que o trabalho precisa ser agendado no momento $ 0 $ e que $ c (0 )= 0 $ .

Deixe $ op [t, p] $ seja a quantidade mínima de orçamento que precisa ser gasto para agendar o trabalho na primeira $ t $ slots com uma penalidade global de no máximo $ P $ e com a restrição adicional que o trabalho deve ser agendado em tempo $ t $ .

Deixe $ p (t ', t)=big \ lFlor \ frac {t-t'-1} {2} \ big \ rfloor $ ser A penalidade incorrida se o trabalho é agendado às vezes $ t '$ $ e $ t> t' $ e não está agendado a qualquer momento entre.

Então $ opt [0, p]= 0 $ e, para $ t> 0 $ : $$ Opt [t, p]= c (t) + \ min _ {\ subestack {t '= 0, \ dots, t-1 \\ p (t', t) \ le p}} opt \ esquerda [t ', p - p (t ', t) \ direita] $$

a penalidade mínima atingível até o tempo $ t $ , com a restrição que o trabalho está agendado no momento $ t $ , é então: $$ \ mu (t)=min {p \ in {1, \ DOTS, \ lFloor t / 2 \ rfloor \} \ mid opt [t, p] \ le b} $$

e a penalidade mínima atingível para o seu problema é: $$ \ min_ {t= 0, \ dots, n} \ left \ {\ mu (t) + p (t, n + 1) \ direito \}. $$

Observe que existem no máximo $ n \ Cdot (p (0, n) +1)= O (n ^ 2) $ valores $ opt [p, t] $ para calcular.