Voisinages pour les problèmes d'ordonnancement juste-à-temps

Yann Hendel et Francis Sourd
LIP6

Résumé:

Dans cet exposé, deux approches différentes seront présentées pour
calculer efficacement des voisinages pour le problème d'ordonnancement
à une machine et pénalités d'avance et de retard. Le fait d'avoir
un critère d'optimisation irrégulier complique en effet les choses:
contrairement aux problèmes avec un critère régulier, l'ordonnancement
optimal n'est pas nécessairement un ordonnancement au plus tôt.

Dans la première approche, des structures de données spécifiques sont
mises en oeuvre pour trouver le meilleur voisin lorsqu'on effectue une
modification de la séquence, ce qui implique une modification des dates
d'exécution des tâches.

La seconde approche est une généralisation de la méthode DYNASEARCH
introduite pour la minimisation des retards (1||\sum Ti). Cette méthode
permet d'explorer en temps polynomial un voisinage de taille exponentielle.
Notre adaptation permet de prendre en compte les release dates, les setups
et les coûts d'avance mais le temps d'exploration du voisinage est 
pseudo-polynomial.