CHAPITRE I. LE PROBLÈME D'EMPLOI DE TEMPS
la résolution se limite à la réponse par
« oui »» ou par « non ». Par contre, un
Problème de recherche est un problème dont sa
résolution ne s'arrête plus au point de savoir si le
problème admet ou non une solution, mais, l'algorithme doit être
capable de trouver la solution en question si elle existe. Par
conséquent, tout problème de décision peut être
étendu à un problème de recherche.
Un problème d'optimisation combinatoire
est obtenu à partir d'un problème de recherche en
associant d'une manière injective à chaque solution une
seule valeur. Ainsi, l'algorithme de résolution consiste à
trouver parmi l'ensemble des solutions celle qui maximise ou minimise
au mieux la valeur associée.
Le premier type des problèmes d'optimisation
combinatoire englobe les problèmes d'optimisation sans
contraintes, dont la recherche de la solution optimale peut être
s'effectuer en tout point de l'espace de recherche. Ceci est permet
car il y absolument aucune contraintes à respecter. Par contre, si un
problème n'a pas d'objectif à optimiser, mais seulement un
ensemble de contraintes à respecter, il est qualifié comme
problèmes de satisfaction de contraintes.
Un problème d'optimisation mono-objectif
est défini comme la recherche de l'opti-mum pour un seule
objectif, si c'été pour deux, on dit que c'est un
problème quadratique et si c'été plus, ce
qui forme un vecteur de fonctions objectif, on dit que c'est un
problème multi-objectif.
L'union de ces derniers types de problèmes engendre un
type plus général appelé problèmes
d'optimisation combinatoire multi-objectif avec contraintes.
Lors de l'étude des problèmes, on commence par
les classer, si on parvient à montrer qu'un problème est
polynomial, alors on peut trouver un algorithme exact et efficace pour le
résoudre en temps polynomiale. Par contre, si on parvient à
montrer qu'il est NP-complet ou NP-difficile, alors la recherche d'un
algorithme exact ne sera pas de première priorité, il est
approprié de se concentrer sur des méthodes
heuristiques.
Une méthode heuristique est souvent définie
comme une procédure exploitant au mieux la structure du problème
considéré, dans le but de trouver une solution de qualité
raisonnable en un temps aussi faible que possible.
I.3 Le problème d'emploi de temps (TTP)
Parmi l'ensemble des problèmes de planification
d'horaire, on repère celui de l'emploi du temps qui semble être au
premier moment très difficile. La notion de difficulté prend son
sens --exclusivement dans cette section-- dans la réalisation manuelle
de ce dernier, car il demande la participation de plusieurs personnes aptes et
capables de prendre des décisions cruciales, qui peuvent se durer
plusieurs jours afin de mettre en oeuvre un emploi de temps acceptable.
Or, la modification d'une donnée du problème initial peut
changer complètement la solution trouvée, et par fois sa demande
de recommencer à zéro le même travail.
5
| 
