Planification pour minimiser les lacunes tronquées

Question

J'ai un seul travail de longueur unitaire, un ensemble de $ n $ emplacements et un budget de $ B $ unités. Si le travail est prévu à la fente $ t $ , il suffira de $ C (t) $ unités du budget $ B $ . Si le travail n'est pas prévu pour une période de $ x $ emplacements consécutifs, puis une pénalité de $ \ lflfor x / 2 \ rfloor $ se produit. L'objectif est de planifier le travail afin de minimiser la somme des sanctions.

Par exemple, pour $ N= 12 $ , si le travail est programmé à la machine à sous 1, à Slot 3, à Slot 6 et à Slot 12 $ , puis la somme des pénalités est $ \ lfloor 1/2 \ rfloor + \ lflfor 2/2 \ rfloor + \ lflfor 5 / 2 \ rfloor= 0 + 1 + 2= 3 $ .

est ce problème np-dur?

J'essaie de réduire le problème du sac à dos. Transformer les valeurs dans le problème du knapsack aux pénalités est difficile, car une fois que le travail est programmé à $ t $ , la pénalité est initialisée.

Answer 1

Le problème est résistant aux polynômes résolvables. Pour éviter les cas de bord, il est préférable de penser que le travail doit être programmé à l'heure 0 $ et que $ C (0 )= 0 $ .

let $ opt [t, p] $ soit le montant minimum de budget à utiliser afin de planifier le travail dans la première catégorie $ T $ Slots avec une pénalité globale d'au plus $ P $ et avec la contrainte supplémentaire que le travail doit être programmé à temps $ t $ .

let $ p (t ', t)=big \ lfloor \ frac {t-t'-1} {2} \ big \ rfloor $ soit La peine engagée si le travail est programmé à l'époque $ t '$ et $ t> t' $ et n'est pas programmé à tout moment entre les deux.

alors $ opt [0, p]= 0 $ et, pour $ t> 0 $ : $$ Opter [t, p]= c (t) + \ min _ \ \ remplacer {t '= 0, \ points, t-1 \\ p (t', t) \ le p}} opt \ gauche [t ', p - p (t ', t) \ droite] $$

La pénalité réalisable minimale jusqu'à la date $ t $ , avec la contrainte que le travail est programmé à l'heure $ t $ est alors: $$ \ mu (t)=min \ {p \ in \ {1, \ dots, \ lfloor T / 2 \ rfloor \ \ \ \ mid opt [t, p] \ le b \} $$

et la pénalité minimale réalisable pour votre problème est la suivante: $$ \ min_ {t= 0, \ dots, n} \ gauches \ \ mu (t) + p (t, n + 1) \ droite \}. $$

Notez qu'il existe au plus $ n \ CDOT (p (0, n) +1)= O (n ^ 2) $ valeurs $ opt [p, t] $ pour calculer.