CHAPITRE I. LE PROBLÈME D'EMPLOI DE TEMPS
I.6 L
|
'aspect combinatoire du problème TTP
|
La mise en oeuvre d'un emploi de temps pour une journée
est facile, car le nombre des combinaisons possible est infime. Cependant, un
emploi de temps mensuel ou annuel dont le nombre de combinaisons est
très grand, ça sera beaucoup plus compliqué. Lorsque des
solutions sont connues auparavant, une négociation permet de
sélectionner la solution pertinente. En effet, chaque acteur
négociant pourra donner son opinion, les points d'accord serons
immédiatement accepter et les points litigieux serons discutés
afin de trouver des solutions de compromis. La difficulté de
négociation augmente avec l'augmentation de nombre d'ac-teurs et plus
particulièrement avec l'augmentation de nombre des solutions
(combinaisons) admissibles, ainsi l'aspect combinatoire prend son sens et rend
plus difficile la négociation.
I.7 Conclusion
Le problème de l'emploi du temps est un problème
classique de la recherche opérationnelle qui trouve son application dans
plusieurs domaines.
La plupart des chercheurs ont consacré leurs recherches
sur l'emploi de temps éducatif (examen ou cours) [22, 11], et la version
la plus simple est celle de « classe-professeur
»présenté par Werra en1985 [6]. Cette version se
concentre sur les contraintes agissant seulement sur les conflits produits par
l'affectation des classes et des professeurs. Cependant, d'autres contraintes
peuvent être ajoutées pour augmenter l'efficacité de
l'emploi, mais ceci augmente considérablement la complexité du
problème.
Le problème d'emploi de temps est un problème
d'optimisation combinatoire de nature multi- objectif et de la classe
NP-complet [4]. Pour ces raisons, il est considérer comme un
repère pour tester les différentes méta-heuristiques.
Une méta-heuristique est l'outil critique en termes
d'algorithme utilisée pour résoudre le problème d'emploi
de temps. Ces méthodes sont généralement de type
stochastique itératif, permettant d'une manière intelligente de
s'échapper de l'optimum local et de s'approcher vers l'optimum
global.
Selon la littérature, plusieurs approches
méta-heuristiques ont été adaptées au
problème d'emploi du temps : S.Elmohamed, P.Coddington et G.Fox ont
utilisé le recuit simulé [20], par contre, A.Schaerf a
utilisé la méthode tabou [3], la même méthode mais
avec deux versions (avec ou sans la recherche local) a été
utilisée par A.Colorni, M.Dorigo et V.Maniezzo. Les mêmes auteurs
ont utilisés aussi une version d'un algorithme génétique
[2]. D.Abramson et j.Abela ont proposé un algorithme
génétique parallèle [5]. M.Chiarandini, M.Birattari,
K.Socha et O.Rossi-Doria ont utilisé une multiple hybridations entre
plusieurs méta-heuristiques, essentiellement la méthode tabou et
le recuit simulé, afin de trouver la bonne configuration qui permet de
résoudre au mieux le problème en 2006 [18].
Enfin, un groupe surnommé ASAP travaille dans ce
contexte, ces membres ont utilisé la majorité des
méta-heuristiques et ils ont fourni des résultats
expérimentaux consternant les configurations (paramètres) qui
nous amènera à des bonnes solutions [10, 11].
8
| 
