Ordonnancement préemptif autour d'une date de fin commune

Francis Sourd (LIP6)

On s'intéresse à un problème d'ordonnancement où l'ensemble 
des tâches doit être livrée à une date donnée d.
La préemption étant autorisée, on introduira un nouveau
critère d'optimisation permettant de modéliser les coûts
d'avance et de retard dans un contexte "Juste-à-temps".

Un algorithme en O(n2) est proposé. Il est basé sur 
la formulation duale du problème qui permet d'exprimer le 
problème comme un problème paramétré de géométrie algorithmique, 
ce qui permettra d'insérer de belles figures dans la 
présentation.