Programación para minimizar las brechas truncadas.

Question

Tengo un solo trabajo de longitud de la unidad, un conjunto de $ n $ slots, y un presupuesto de $ b $ unidades. Si el trabajo está programado en Slot $ t $ , entonces consumirá $ c (t) $ unidades del presupuesto $ b $ . Si el trabajo no está programado para un período de $ x $ tragamonedas consecutivas, luego una penalización de $ \ lfloor x / 2 \ rfloor $ ocurre. El objetivo es programar el trabajo para minimizar la suma de sanciones.

Por ejemplo, para $ n= 12 $ , si el trabajo está programado en la ranura 1, en la ranura 3, en la ranura 6, y en la ranura $ 12 $ , entonces la suma de sanciones es $ \ lfloor 1/2 \ rfloor + \ lfloor 2/2 \ rfloor + \ lfloor 5 / 2 \ rfloor= 0 + 1 + 2= 3 $ .

¿Es este problema NP-HARD?

Estoy tratando de reducir el problema de Knapsack. Transformar los valores en el problema de la mochila a las sanciones es de alguna manera difícil, porque una vez que el trabajo está programado en $ t $ , se inicializa la penalización.

Answer 1

El problema es el tiempo de polinómico solvable. Para evitar casos de bordes, es mejor pensar que el trabajo debe programarse en el momento $ 0 $ y ese $ c (0 )= 0 $ .

Let $ opt [t, p] $ Sé la cantidad mínima de presupuesto que debe gastarse para programar el trabajo en la primera $ t $ ranuras con una penalización general de más $ P $ y con la restricción adicional de que el trabajo debe programarse en Tiempo $ t $ .

Let $ P (t ', t)=big \ lfloor \ frac {t-t'-1} {2} \ big \ rfloor $ be La penalización incurrió en que el trabajo está programado en Times $ t '$ y $ t> t' $ y no está programado en ningún momento intermedio.

luego $ opt [0, p]= 0 $ y, para $ t> 0 $ : $$ Opt [T, P]= C (t) + \ min _ {\ bufch {t '= 0, \ dots, t-1 \\ p (t', t) \ le p (t ', t) \ le p (t', t) \ le p (t ', t) \ le p (t', t) \ le p (t ', t) \ le p (t', t) \ le p (t ', t) \ le p (t', t) \ le p (t ', t) \ le p (t', t '\ le p}} Opt \ Izquierda [T', P - P (T ', T) \ Derecha] $$

La multa mínima alcanzable hasta el tiempo $ t $ , con la restricción de que el trabajo está programado en el momento $ t $ , es entonces: $$ \ mu (t)=min \ {p \ in \ {1, \ dots, \ lfloor t / 2 \ rfloor \} \ mediados opt [t, p] \ le b \} $$

y la multa mínima alcanzable por su problema es: $$ \ min_ {t= 0, \ dots, n} \ izquierda \ {\ m mu (t) + p (t, n + 1) \ derecha \}. $$

Observe que hay en la mayoría de $ n \ cdot (P (0, N) +1)= O (n ^ 2) $ valores $ Opt [P, T] $ para calcular.