Problème d'ordonnancement avance-retard autour d'une date d'échéance
commune avec préemption

Nina Runge (LIP6)

Dans les problèmes d'ordonnancement avec des coûts d'avance et de
retard, l'interruption de certaines tâches peut fournir une solution
améliorée par rapport aux solutions non préemptives. Nous examinons deux
modèles pour le problème d'ordonnancement avance-retard préemptif autour
d'une date d'échéance commune. Selon le modèle choisi, la préemption
peut améliorer la solution optimale. Nous proposons un premier modèle
ayant des solutions optimales préemptives. Pour ce modèle, des règles de
dominance sont présentées. Un algorithme Branch and Bound basé sur ces
règles et utilisant une relaxation lagrangienne résout des instances
jusqu'à 25 tâches en moins de 80 sec. A la fin du papier, un deuxième
modèle est présenté pour lequel nous prouvons qu'il existe toujours une
solution optimale non préemptive.