CHAPITRE 3
LES METHODES DE RESOLUTION
DU PROBLEME D'ORDONNACEMENT
3.1 Introduction :
Plusieurs auteurs [Mac Cathy & Liu 93, ESSWEIN 03]
partitionnent les méthodes de résolution en 3 classes : les
méthodes optimales efficaces, les méthodes
énumératives et les méthodes heuristiques.
· Les méthodes optimales
énumératives sont aussi des algorithmes exactes elles fournissent
en pratique sur des problèmes de taille moyenne, des solutions optimales
en un temps raisonnable .Dans cette classe, on peut distinguer :
ü Les procédures par séparation et
évaluation progressive (SEP)
(Branch&Bound) qui énumèrent par une recherche arborescente
un ensemble de solution en éliminant les branches de l'arbre de
recherche montrées non-optimales (utilisation de bornes
inférieure et supérieure du critère)
ü Les méthodes de programmation linéaires
(PL) modélisant les critères et les contraintes comme des
fonctions linéaires de variables mixtes (réelle, entier).
ü Les méthodes basées sur la programmation
dynamique (PD) qui se décomposent en sous problème, que l'on
résout optimalement à rebours, en tenant compte du
sous-problème précèdent.
· Les méthodes heuristiques sont souvent
utilisées pour traiter des problèmes que les méthodes
optimales sont incapables de les résoudre en un temps acceptable .Elles
produisent généralement une solution faisable de bonne
qualité en un temps relativement court. La qualité d'une
heuristique doit être évaluée sur plusieurs jeux d'instance
de taille variable afin de mesurer d'une part la déviation moyenne du
critère par rapport à sa valeur optimal et d'autre part
l'évolution du temps de calcul en fonction de la taille ou de la
structure du problème. Ces heuristiques sont classifiées en trois
grands types :
ü les algorithmes gloutons dans lesquels les
décisions d'ordonnancement sont prises progressivement, à temps
croissant, au fur et à mesure que les ressources se libèrent,
grâce à des règles de priorité simples de type
SPT(Shortest Processing Time), EDD(Earliest Due Date), etc. ; et pour lesquels
on ne remet jamais en cause une décision qui a été
prise.
ü les méthodes de recherche locale (tabou, recuit
simulé, algorithmes génétiques, etc.) qui, partant d'une
solution initiale, définissent un voisinage, qui est ensuite
exploré pour trouver des solutions meilleures ; (en s'autorisant parfois
à dégrader la solution courante pour augmenter la chance
d'obtenir une solution meilleure).
ü les méthodes de recherche arborescente
tronquée, proches des PSE, excepté que l'arbre de recherche est
volontairement restreint, quitte à perdre des solutions optimales, afin
de gagner en temps de calcul.
| 
