II.4.2.4 Méthodes par relaxation des contraintes
Afin de favoriser l'obtention d'une solution, il est
fait recours dans ces méthodes à une relaxation de certaines
contraintes du problème. La solution de ce dernier aboutira
naturellement à une solution idéale (en ce sens qu'elle ne peut
être atteinte) qui servira de repère lors de la résolution
du problème initial. Ainsi, la solution obtenue sera proche de la
solution idéale, moins optimale mais réalisable.
II.4.2.? Méthodes liées à
l'Intelligence Artificielle
Cette catégorie regroupe des méthodes
dont la principale caractéristique commune se limite à leur
origine I.A. Aussi cette catégorie de méthodes est-elle vaste et
diverse. Il ressort de [GHOT 93] la distinction des sous-classes de
méthodes suivantes :
> Les systèmes à Base de Connaissances
(SBC) dotés de capacité d'apprentissage
> Les règles de priorité
> La propagation des contraintes
> Les algorithmes génétiques
Toutes ces méthodes sont relativement
récentes et en pleine expansion (notamment celles mettant
en oeuvre les algorithmes
génétiques).
27
Dans le chapitre IV on va faire une étude
générale sur les algorithmes génétiques
I.? caractéristiques générales
d'ordonnancement :
Des sous-ensembles d'ordonnancement particuliers sont ici
présentés dont certains présentent des
priorités de dominance vis-à-vis de tout
critère régulier [ESQU 99].
I.5.1 ordonnancement admissible (acceptable) :
Un ordonnancement est dit admissible s'il
respecte toutes les contraintes du problème (dates
limites, précédences, limitation des
ressources,...)
? Exemple : considérons cinq
tâches 1, 2, 3, 4, 5 telles que l'on doive respecter les
contraintes de précédence 1<2<5 et
3<4. Un ordonnancement admissible est représenté à la
Figure 2.
Figure 2 Ordonnancement admissible.
? On parle de glissement à gauche local
lorsqu'on avance le début d'une tâche sans remettre en cause
l'ordre relatif entre les tâches. Sur l'exemple ci-dessus, bien
qu'admissible, la solution pourrait être amélioré du point
de vue du temps total d'exécution, en faisant un glissement local de
certaines tâches vers la gauche (3 et 4 d'une unité, puis 5 de
trois unités).
? On parle de glissement à gauche global
lorsqu'on avance le début d'une tâche en modifiant l'ordre relatif
entre au moins deux tâches. Sur l'exemple précédent, le
repositionnement de la tâche 5 juste au-dessus de la tâche 3 est
admissible mais change la relation 4<5 en 5<4 (Figure 2).
| 
