CHAPITRE I. LE PROBLÈME D'EMPLOI DE TEMPS
Cette difficultés explique pourquoi aujourd'hui on est
besoin d'un ordinateur pour automatiser ces tâches et pour
générer des emplois du temps efficaces dans un temps acceptable
en adoptant des outils basés sur des algorithmes d'optimisation
robustes.
La description générale de ce problème
est la suivante : « le problème de l'emploi du temps consiste
à définir un certain nombre d'affectations qui
permettent d'assigner plusieurs ressources (humaines,
matérielles) sur une période de temps, tout en
respectant certaines contraintes qui peuvent différer
d'un problème à un autre suivant la spécification et les
caractéristiques attendues de l'emploi du temps en question ».
Les contraintes sont souvent classées en deux
catégories : la première regroupe les contraintes dures,
dont l'emploi du temps qui ne les respecte pas sera inacceptable. La seconde
catégorie regroupe des contraintes dites de
préférence, dont la satisfaction décide ce que
doit être le bon emploi du temps, mais dont le non respect
n'empêchera pas de générer un emploi du temps plus au moins
acceptable.
I.4 Classification des problèmes d'emplois de
temps
Selon son cycles du vie, un emploi de temps peut être
quotidien, hebdomadaire, mensuel ou annuel et selon le domaine de
l'application, on qualifie ce dernier par le nom de domaine, comme par exemple
: l'emploi de temps éducatif, de sport, de transport ou de
communication.
Selon la littérature, l'emploi de temps éducatif
est le problème le plus étudié, et il est classé en
deux : l'emploi de temps des cours et l'emploi de temps des examens. Il y a,
naturellement, des différences significatives entre les deux. Par
exemple, un certain nombre d'examens peuvent être programmé dans
une salle, ainsi, un examen peut être passé dans plusieurs salles.
Cependant, un seul cours habituellement doit être programmé dans
exactement une seule salle.
I.5 Une instance de problème TTP
On va consacrer cette section pour décrire une instance
de problème d'emploi de temps éducatif car il est le plus
étudié. Mais ce dernier s'exprime en plusieurs formes dont chaque
forme est spécifique à l'environnement ou à l'institution
qui en a besoin. on va donc choisir notre université (UMBB) comme source
d'inspiration.
Pour notre université, les responsables
pédagogiques ont besoin chaque année d'établir une
nouvelle planification pour les différentes promotions en essayant au
mieux de satisfaire le bien des enseignants et des étudiants, et de
respecter les contraintes imposées par l'adminis-tration et celles qui
sont liées aux ressources.
Le département d'informatique, par exemple, propose
différentes formations, dont leurs programmes pédagogiques sont
connus à priori. Ce programme précise les modules à
suivre, leurs volumes horaires et quelques informations pédagogiques
(répartition en cours, travaux dirigés, travaux pratiques). Selon
les besoins pédagogiques et les ressources disponible, chaque formation
est structurée en promotions, en sections, et en groupes. Le nombre
d'étudiants par groupe en travaux dirigés(TD) est limité
pour assurer un meilleur suivi des étudiants.
6
| 
