mémoire licence aribi 2014 .pdf



Nom original: mémoire_licence_aribi_2014.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.11, et a été envoyé sur fichier-pdf.fr le 11/06/2016 à 13:08, depuis l'adresse IP 193.194.x.x. La présente page de téléchargement du fichier a été vue 371 fois.
Taille du document: 1.4 Mo (48 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)










Aperçu du document



epublique Alg´
erienne D´
emocratique et Populaire
Minist`
ere de l’Enseignement Sup´
erieur et de la Recherche Scientifique
Universit´
e M’hamed Bougara Boumerdes
Facult´
e des Sciences

epartement d’informatiques


emoire Pr´
esent´
e
Du Diplˆ
ome De Licence
En Informatiques
Par : Aribi Mohamed Lamine
Et : Bentaiba Nidhal Wafi

ab
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
bc
ddd
e
e
e
fgggggggggggggggggggggggggggggggggggggggggggh
Conception et r´
ealisation d’une approche
mim´
etique pour le probl`
eme d’emploi de temps

Devant le jury :
.
Madame : Hadjidj.D (E)
.
Madame : Frihi.Ibtissem (P)
.
Madame : Elnagger.Raouiya (M)

Ann´
ee Universitaire 2013 − 2014

Table des mati`eres

Introduction g´en´erale

6

´
1 Etat
de l’art

7

1.1

1.2

Description du Probl`eme de l’emploi du temps :

1.4

7

1.1.1

C’est quoi la planification :

. . . . . . . . . . . . . . . . . . . . . . . . .

7

1.1.2

C’est quoi un planning : . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.3

Comment ´evaluer un planning : . . . . . . . . . . . . . . . . . . . . . . .

8

1.1.4

Qui peut se charger de l’´elaboration d’un planning : . . . . . . . . . . . .

8

Les diff´erents types de plannings : . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.1

Type de planning dans le domaine de la sant´e . . . . . . . . . . . . . . .

9

1.2.2

Type de planning dans le domaine de transport : . . . . . . . . . . . . .

9

1.2.3
1.3

. . . . . . . . . . . . . . . . .

Type de plannings dans le domaine p´edagogique :

. . . . . . . . . . . .

9

Notion de complexit´e : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1

Complexit´e en temps : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.2

Complexit´e en espace :

1.3.3

Les diff´erentes classes de complexit´e : . . . . . . . . . . . . . . . . . . . . 11

. . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Les m´ethodes internes utilis´ees dans la r´ealisation du probl`eme de l’emploi de
temps : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.1

M´ethode exacte et m´ethode approch´ee : . . . . . . . . . . . . . . . . . . 12

1.4.2

M´ethode heuristique de type recherche Tabou : . . . . . . . . . . . . . . 13

1.4.3

Programmation par contraintes : . . . . . . . . . . . . . . . . . . . . . . 13

1.4.4

Les algorithmes g´en´etiques : . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.5

Les m´ethodes m´eta heuristiques : . . . . . . . . . . . . . . . . . . . . . . 14

1.4.6

La m´ethode mim´etique : . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1

`
TABLE DES MATIERES

2
2 Approche mim´
etique

17

2.1

Introduction a` l’algorithme M´em´etique (MA) : . . . . . . . . . . . . . . . . . . . 17

2.2

Explication : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3

Croisement [th997] : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4

2.5

2.3.1

Le croisement a` un point : . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.3.2

Le croisement a` deux points . . . . . . . . . . . . . . . . . . . . . . . . . 19

Mutation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1

Mutation binaire : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.2

Mutation r´eelle : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.4.3

Mutation non uniforme :

Recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1

2.6

. . . . . . . . . . . . . . . . . . . . . . . . . . 21

Basic de la recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . 21

Algorithme de la recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Description du probl`
eme :

24

3.1

Aspect G´en´erale :

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.2

Les contraintes dures : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.3

Les Contraintes de Pr´ef´erence (souples) : . . . . . . . . . . . . . . . . . . . . . . 26

4 R´
esolution et Structures

27

4.1

Les structures de donn´ees utilis´ees : . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2

Les contraintes : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3

4.2.1

Contrainte souple de la solution : . . . . . . . . . . . . . . . . . . . . . . 29

4.2.2

Contraintes dures de la solution : . . . . . . . . . . . . . . . . . . . . . . 31

L’algorithme memetique : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1

Cr´eation de la population initiale : . . . . . . . . . . . . . . . . . . . . . 32

4.4

Croisement : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.5

Mutation : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.6

La recherche locale : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5 Impl´
ementation

39

5.1

Les outils utilis´es dans la r´ealisation de cette application :

5.2

Pr´esentation de l’application : . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Pr´esent´e par : A.M et B.W

. . . . . . . . . . . . 39

UMBB

3

Pr´esent´e par : A.M et B.W

`
TABLE DES MATIERES

UMBB

4

Pr´esent´e par : A.M et B.W

`
TABLE DES MATIERES

UMBB

5

Pr´esent´e par : A.M et B.W

`
TABLE DES MATIERES

UMBB

Introduction g´en´erale

Dans plusieurs domaines de la vie professionnelle, on se trouve confront´e au probl`eme de la
planification de l’emploi du temps, cela diff`ere d’une organisation a` une autre, puisque chacune
poss`ede ses propres normes et crit`eres. Par exemple, dans un hˆopital il existe un certain nombre
de personnel tels que des m´edecins, des infirmiers, etc. qui doivent ˆetre attribu´es aux postes de
travail en respectant certaines r`egles de gestion hospitali`ere.
Dans une universit´e on a un personnel enseignant, un ensemble de salles, des amphith´eˆatres,
des salles de TP, etc. On doit les organiser dans le but de satisfaire les contraintes humaines des
enseignants et des ´etudiants et les contraintes p´edagogiques et on tenant compte des contraintes
physiques li´ees aux ressources mat´erielles (salles, ´equipements, etc.). La planification du temps
consiste `a allouer des ressources donn´ees a` des objets dans un intervalle de temps de fa¸con a`
satisfaire certains objectifs comme l’am´elioration de la qualit´e de service et l’am´elioration des
conditions de travail.
Ce probl`eme est consid´er´e comme une affaire ardue dont la mise en main est une tˆache difficile
qui peut mobiliser plusieurs personnes et plusieurs jours de travail. Sans oublier que toute modification des donn´ees du probl`eme peut compl`etement remettre en cause la solution trouv´ee.
Ces difficult´es ont provoqu´e l’id´ee d’utiliser la machine (ordinateur) pour l’´elaboration des emplois du temps en adoptant des outils bas´es sur des algorithmes d’optimisation efficaces.
G´en´eralement le probl`eme de l’emploi du temps consiste a` d´efinir un certain nombre d’affectations permettant d’allouer plusieurs ressources (humaines, mat´eriels, etc. sur un intervalle de
temps, en respectant les contraintes impos´ees par les entit´es pr´ec´edemment cit´ees).
(Disponibilit´e des ressources humaines et mat´erielle, etc.).
Les contraintes peuvent ˆetre class´ees en deux cat´egories :
• Contraintes dures : qui doivent ˆetre satisfaites, donc l’emploi du temps qui ne les
satisfait pas est inacceptable.
• Contraintes souples : (molles ou bien Inattentives) dont la satisfaction a diff´erents
degr´es d’importance, mais dont le non respect n’empˆeche pas une application plus ou
moins acceptable de l’emploi du temps trouv´e. Elles sont plus difficiles a` formaliser que
les contraintes dures. Donc elles sont introduites comme une fonction objective qu’il faut
optimiser afin de se rapprocher le plus possible de la satisfaction de ces contraintes.
La confection de l’emploi du temps est un processus tr`es demand´e pour l’organisation du
travail. Son importance augmente vu la progression de la complexit´e des probl`emes consid´er´es.
Depuis les ann´ees 60 l’int´erˆet de la g´en´eration de l’emploi du temps a augment´e avec la
disponibilit´e des ordinateurs qui peuvent ex´ecuter les algorithmes d´evelopp´es.

6

1

´
Etat
de l’art

Introduction :
On s’int´eresse dans ce chapitre de la mise en sc`ene de ce probl`eme, ainsi que l’aspect
g´en´eral de cette probl´ematique, sa complexit´e et son importance dans la vie professionnelle. On ´evoquera quelques d´efinitions introductives au probl`eme, aux diff´erents types de
ce probl`eme et les m´ethodes propos´ees pour la r´esolution de ce probl`eme, mais on ´etudiera
le probl`eme de la gestion de l’emploi du temps dans le domaine p´edagogique de fa¸con sp´ecifique.

1.1

Description du Probl`
eme de l’emploi du temps :

Ce probl`eme se retrouve autant dans les entreprises d’industrie que dans les services publics
telle que la sant´e, l’´education, etc.
La planification de l’horaire de travail est un processus tr`es complexe qui s’int´eresse a` organiser
des activit´es humaines dans le temps et optimiser l’utilisation des ressources. Pour comprendre
c’est quoi la planification du temps et la complexit´e de sa r´ealisation, on s’int´eresse `a un
ensemble de questions.

1.1.1

C’est quoi la planification :

La planification consiste `a affecter des ressources humaines `a des intervalles de temps pour
assurer des services en satisfaisant les diff´erentes contraintes et r´ealiser les buts d´efinis au
d´epart.
Par exemple dans le cas d’une universit´e, la gestion de l’emploi du temps met en relation trois
7

´
CHAPITRE 1. ETAT
DE L’ART

8

diff´erentes ressources : les enseignants, les salles et les ´etudiants.
Trois acteurs poss´edant chacun un rˆole bien d´efini se confrontent pendant la gestion de l’emploi
du temps :
• l’administrateur qui doit g´erer (ajouter, supprimer) les ressources.
• Le responsable de formation qui r´ealise l’affectation des enseignements aux enseignants.
Il peut ´egalement r´esoudre les conflits et les disponibilit´es des diff´erentes ressources du
syst`eme.
• L’enseignant qui utilise son agenda pour g´erer son emploi du temps. Il peut mettre `a jour
des ´ev`enements et consulter d’autres enseignants.
Tout ceci doit ˆetre orient´e afin d’optimiser les ressources et le volume des cours donn´es.

1.1.2

C’est quoi un planning :

C’est un calendrier de travail. Il contient a` la fois le temps, les affectations du personnel,
les jours et les horaires de travail, ainsi que les jours de repos.
La r´ealisation d’un bon planning implique a` la fois une n´egociation efficace entre le planificateur
et les diff´erents employ´es concern´es. Et afin de minimiser le cout et maximiser le profit, on
doit r´ealiser un calcul d’optimisation combinatoire. [th003].

1.1.3

Comment ´
evaluer un planning :

Pour que le planning r´ealis´e soit acceptable, il doit satisfaire un ensemble de contraintes
et ´etablir un meilleur compromis entre les diff´erents acteurs (ex : chef d’entreprise, salari´e,
superviseur, etc.).
Lorsque les diff´erentes solutions alternatives sont connues, une n´egociation se d´eroule de la
mani`ere suivante : chaque acteur donne son opinion. Les points d’accord sont tr`es vite exp´edi´es,
les points de contentieux sont d´ebattus et les solutions de compromis sont d´egag´ees.
Les difficult´es de la n´egociation d´ependent du nombre des acteurs et des solutions alternatives,
mais les moyens informatiques apportent une aide certaine, surtout dans l’acquisition puis la
confrontation des donn´ees individuelles. [th002].

1.1.4

Qui peut se charger de l’´
elaboration d’un planning :

Dans la majorit´e des entreprises cette tache peut ˆetre centralis´ee ou bien d´el´egu´ee a` des
cadres de l’entreprise appel´es planificateurs.
Le planificateur doit prendre les d´ecisions qui correspondent aux pr´ef´erences des diff´erents
acteurs, justifier son choix pour ´evaluer rapidement et effectuer des jugements de l’orientation
a` donner a` la recherche des meilleures solutions pour aboutir a` un choix pertinent.

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

9

1.2

Les diff´
erents types de plannings :

Si la r´ealisation d’un planning de travail optimale pour une journ´ee est facile, ou bien
simple ; la cr´eation d’un bon planning qui va ˆetre utilis´e durant un mois, ou bien une ann´ee
est beaucoup plus complexe. Il faut prendre en compte la diversit´e des contraintes applicables,
sans oublier la complexit´e combinatoire du probl`eme.
Pour ce qui suit on va voir les diff´erents types de plannings.

1.2.1

Type de planning dans le domaine de la sant´
e

Dans ce domaine les plannings sont des calendriers de travail o`
u on trouve a` la fois le temps
et l’affectation des personnels (jours et horaires de travail, cong´es et repos).
Parmi les contraintes qu’on doit les respecter, on peut citer :
• En cas de travail continu, la dur´ee quotidienne de travail ne peut exc´eder 9 heures pour
les ´equipes de jour, 12 heures pour les ´equipes de nuit.
• Le nombre de jours de repos est fix´e a` 4 jours pour 2 semaines.
• L’infirmier ne peut pas travailler dans une journ´ee alors qu’il a travaill´e la nuit pass´ee.
[th015].
Plusieurs m´ethodes ont ´et´e utilis´es afin de r´esoudre ce probl`eme : telle que la programmation
par contraintes, la recherche locale, les algorithmes ´evolutionnaires ... etc.

1.2.2

Type de planning dans le domaine de transport :

Le transport est un domaine tr`es important dans la vie, c’est une activit´e n´ecessaire mais
complexe et difficile a` g´erer. Elle a besoin de personnel qualifi´e, des investissements lourds et
des outils informatiques tr`es couteux.
Dans le domaine des transports, il faux g´erer les ressources disponibles en optimisant les
investissements. Il faut offrir des services sur mesure, g´erer le personnel et planifier toujours en
temps r´eel en tenant compte plusieurs contraintes (contrat, temps de travail, le coˆ
ut, etc.) car
les clients demandent toujours les meilleurs services et de la flexibilit´e.

1.2.3

Type de plannings dans le domaine p´
edagogique :

La r´ealisation de l’emploi du temps dans les ´etablissements scolaires est un probl`eme de
r´esolution des contraintes, NP-complet, dont la solution n’est g´en´eralement pas connue. Il faut
fournir une solution capable de s’adapter aux changements dynamiques qui peuvent arriver
de temps en temps en tenant compte des diff´erentes contraintes telles que la corr´elation des
programmes d’enseignement, la disponibilit´e des salles, le genre de cours, la disponibilit´e des
enseignants et la dur´ee des cours.
Ce probl`eme peut ˆetre divis´e en deux : l’´elaboration de l’emploi du temps des cours et la
confection de l’horaire des examens.
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

10

Plusieurs approches et mod`eles ont ´et´e propos´es pour diff´erents probl`emes d’emploi du temps.
Les premiers plannings ont ´et´e effectu´es manuellement. Une fois que le planning est r´ealis´e
il reste statique et a` chaque fois on fait les modifications n´ecessaires pour qu’il devienne
appropri´e aux nouveaux cas rencontr´es, mais avec le temps des changements ont ´et´e rencontr´es
dans le domaine p´edagogique. Donc l’emploi du temps pr´ec´edent est devenu inefficace. Par
cons´equent le besoin de la g´en´eration automatis´ee d’emploi du temps augmente et ainsi, le
d´eveloppement d’un syst`eme de g´en´eration d’emploi du temps produit des solutions valables,
efficaces et raisonnables.

Les contraintes qu’on doit satisfaire lors de la r´
ealisation d’un emploi du
temps : Lorsqu’on r´ealise un planning d’utilisation du temps on doit penser `a quelques cas
particuliers ind´esirables. Ces adventifs doivent ˆetre r´egl´es dans le but d’obtenir un bon emploi
du temps qui arrange tout les acteurs de l’entreprise afin d’´eviter tout risque de conflits. Ces
contraintes peuvent ˆetre partitionn´ees en deux cat´egories : contraintes dures et contraintes
souples.
• contraintes dures : Ce type de contraintes doit ˆetre obligatoirement satisfait dans toutes
les situations car la violation de l’une de ces contraintes rend l’emploi du temps inefficace.
On citera quelques exemples ult´erieurement dans notre m´emoire.
• Les contraintes souples : Contrairement au type de contraintes pr´ec´edent, ce genre de
contraintes n’exige pas la v´erification stricte, mais d’approcher au maximum de l’objectif
voulu. On les citera ult´erieurement dans notre m´emoire.

1.3

Notion de complexit´
e:

D’une mani`ere g´en´erale, pour r´esoudre un probl`eme, on est appel´e a` trouver l’algorithme
le plus efficace. Cette notion d’efficacit´e induit normalement toutes les ressources de calcul
n´ecessaires pour ex´ecuter un algorithme.
L’efficacit´e d’un algorithme peut ˆetre ´evalu´ee en temps et en espace :
• complexit´
e en temps : ´evaluation du temps d’ex´ecution de l’algorithme.
• complexit´
e en espace : ´evaluation de l’espace m´emoire occupe par l’ex´ecution de l’algorithme

1.3.1

Complexit´
e en temps :

Le temps d’ex´ecution est g´en´eralement le facteur dominant pour d´eterminer si un algorithme
est assez efficace pour ˆetre utilis´e dans la pratique. Pour cela on se concentre principalement
sur cette ressource.
On appelle complexit´e en temps d’un algorithme le nombre d’instructions ´el´ementaires mises en
oeuvre dans cet algorithme afin de r´esoudre un probl`eme donn´e. Une instruction ´el´ementaire
sera une affectation, une comparaison, une op´eration alg´ebrique, la lecture et l’´ecriture, etc.
Mais comme le d´ecompte pr´ecis de toutes les instructions d’un programme risque d’ˆetre assez
difficile, et qu’entre deux ex´ecutions du mˆeme algorithme avec un jeu de param`etres diff´erents,
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

11

le nombre d’instructions ex´ecut´ees peut changer. Il suffit en g´en´eral, d’appr´ecier un ordre de
grandeur de ce nombre d’instructions. C’est ce qu’on d´esigne sous le nom de complexit´e de
l’algorithme. Donc, pour mesurer la complexit´e temporelle d’un algorithme, on s’int´eresse plutˆot
aux op´erations les plus coˆ
uteuses :
• Racine carr´ee, Log, Expo, Addition r´eelle,...etc.
• Comparaisons dans le cas des tris,...etc.
Il est possible d’´evaluer de fa¸con exp´erimentale le temps d’ex´ecution des programmes.
***** Graphe de nivaux de complexit´
e temporelle *****

Cette ´evaluation exp´erimentale d´epend beaucoup des langages de programmation, ordinateurs
et syst`emes d’exploitation utilises.

1.3.2

Complexit´
e en espace :

Pour gagner du temps de calcul, on doit utiliser d’avantage d’espace m´emoire. Mais ce
genre de complexit´e n’a pas d’int´erˆet car le probl`eme de l’espace m´emoire a ´et´e r´egl´e. On
peut dire que les mˆemes notions qui traitent la complexit´e temporelle permettent de traiter la
complexit´e spatiale. [th0016], [th0017], [th0018].

1.3.3

Les diff´
erentes classes de complexit´
e:

La class P :
La classe P ” Polynomial time ” contient tous les probl`emes relativement faciles (faisables),
c’est a` dire ceux pour lesquels on connaˆıt des algorithmes efficaces. Plus formellement, ce
sont les probl`emes pour lesquels on peut construire une machine d´eterministe dont le temps
d’ex´ecution est de complexit´e polynomiale. Un probl`eme est dit de la classe P s’il peut ˆetre
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

12

d´ecid´e par une machine de turing d´eterministe en temps polynˆomiale.
Exemple (Connexit´
e dans un graphe) :
´
Etant donn´e un graphe a` n sommets, il s’agit de savoir si le graphe est connexe, en appliquant
un algorithme de marquage. Si on trouve que toutes les paires de sommets sont reli´ees par un
chemin donc le graphe est connexe. Le temps n´ecessaire pour parcourir l’algorithme est calcul´e
par la loi suivante : t= C.n2
(C :est un cte et n le nombre des sommets, donc le probl`eme est de la class P). [th666].
La classe NP :
Les probl`emes de la classe NP sont ceux pour lesquels on peut construire une machine de
Turing non d´eterministe dont le temps d’ex´ecution est de complexit´e polynomiale (le sigle NP
provient de Non deterministic Polynomial time ) (et non de Non Polynomial ).

La class NP-complet :
Parmi les diff´erents probl`emes inclus dans la class NP il existe une classe qui contient les
probl`emes les plus difficiles. On l’appelle probl`emes NP-complet. Tout les probl`emes de NP
peuvent ˆetre r´eduits en un probl`eme NP-complet. C’est `a dire qu’un probl`eme est NP-complet
quand tous les probl`emes appartenant a` NP lui sont r´eductibles.
Plusieurs probl`emes sont consid´er´e comme NP-complet telle que probl`emes de tourn´ees,
d’emploi du temps, placement de taches, affectation de fr´equences, rotation d’´equipages,
d´ecoupage, etc.

1.4

Les m´
ethodes internes utilis´
ees dans la r´
ealisation
du probl`
eme de l’emploi de temps :

Les probl`emes de l’emploi du temps ont attir´e la communaut´e scientifique qui inclut la RO
(Recherche Op´erationnelle) et l’IA (intelligence artificielle) pour environ 40 ans et au cours des
derni`eres ann´ees plusieurs m´ethodes ont ´et´e d´ecrites.
Plusieurs m´ethodes ont ´et´e propos´ees afin de trouver des solutions efficaces pour ce probl`eme,
chaque m´ethode a ses propres ´etapes et caract´eristiques. On va citer quelques exemples de ces
m´ethodes.

1.4.1


ethode exacte et m´
ethode approch´
ee :

Une recherche exhaustive par ´enum´eration explicite de toutes les solutions est impensable
pour r´esoudre un probl`eme d’optimisation difficile en raison du temps de calcul induit.
N´eanmoins, la r´esolution d’un tel probl`eme d’optimisation peut se faire de mani`ere exacte en
mod´elisant soigneusement le probl`eme puis en appliquant un algorithme ad-hoc, qui ´ecarte
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

13

d’embl´ee l’examen de certaines configurations dont on sait d’ores et d´ej`a qu’elles ne peuvent
pas ˆetre optimales.
Parmi les m´ethodes exactes, on trouve la plupart des m´ethodes traditionnelles (d´evelopp´ees
depuis une trentaine d’ann´ees) telles les techniques de s´eparation et ´evaluation (branch-andbound), ou les algorithmes avec retour arri`ere (backtracking). Les m´ethodes exactes ont permis
de trouver des solutions optimales pour des probl`emes de taille raisonnable. Mais malgr´e les
progr`es r´ealis´es (notamment en mati`ere de programmation lin´eaire en nombres entiers), comme
le temps de calcul n´ecessaire pour trouver une solution risque d’augmenter exponentiellement
avec la taille du probl`eme. Les m´ethodes exactes rencontrent g´en´eralement des difficult´es avec
les applications de taille importante.
Si les m´ethodes de r´esolution exactes permettent d’obtenir une ou plusieurs solutions dont
l’optimalit´e est garantie, dans certaines situations, on peut cependant se contenter de solutions
de bonne qualit´e, sans garantie d’optimalit´e, mais au profit d’un temps de calcul r´eduit. On
utilise pour cela une m´ethode heuristique adapt´ee au probl`eme consid´er´e, avec cependant
l’inconv´enient de ne disposer en retour d’aucune information sur la qualit´e des solutions
obtenues.

1.4.2


ethode heuristique de type recherche Tabou :

La recherche tabou est une m´ethode m´eta-heuristique de recherche locale a` partir d’une
solution initiale dans un voisinage pr´ed´efini. L’algorithme parcourt le voisinage de l’espace
de solutions depuis la solution initiale, de fa¸con non ordonn´ee. Le voisinage est d´efini par
un ensemble de types de transitions d’´etat. On ne retient que la solution qui poss`ede une
´evaluation meilleure a` celle obtenue auparavant.
Afin d’´eviter de revenir sur une solution d´ej`a visit´ee, le syst`eme maintient une liste de
transitions r´ecentes qui sont d´eclar´ees interdites, d’o`
u le nom tabou. Cette liste fonctionne
comme une pile. Les ´el´ements seront tabou pendant un nombre K d’it´erations. Ainsi, faute de
trouver une solution avec une meilleure ´evaluation, on peut accepter une qui n’est pas sur la
liste tabou.
Cette technique dispose d’un m´ecanisme permettant de retenir une solution malgr´e le tabou :
un crit`ere d’aspiration souvent utilis´e est bas´e sur le taux d’am´elioration de la fonction
d’´evaluation. Si la solution est tr`es bonne par rapport `a la solution courante, on l’accepte
malgr´e son inscription sur la liste tabou. [th003].

1.4.3

Programmation par contraintes :

Cette m´ethode qui tire profit de plusieurs autres disciplines : math´ematiques, analyse
num´erique, recherche op´erationnelle, intelligence artificielle et calcul formel, a prouv´e son
efficacit´e dans de nombreux domaines. L’objectif de l’approche propos´ee dans ce cas est de
d´evelopper un mod`ele de programmation par contraintes pour la r´ealisation d’un emploi du
temps permettant de mod´eliser des contraintes complexes et fournir de bonnes solutions.
[th0010].
Il existe un outil d’aide `a l’´elaboration des emplois du temps ¡¡Gymnaste¿¿ qui a ´et´e d´evelopp´e
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 1. ETAT
DE L’ART

14

pour la r´esolution de ce probl`eme : il s’int´eresse `a mettre en main un logiciel d’aide `a la
planification.
Le principe de cette approche est la collaboration homme-machine : l’utilisateur doit appr´ecier
(estimer) les facteurs humains n´ecessaires `a la planification et c’est `a la machine de r´esoudre le
probl`eme propos´e de fa¸con optimale. Grace a` la programmation par contraintes, sa souplesse et
sa dynamicit´e on peut collaborer entre les algorithmes efficaces et l’intelligence humaine. [th007].

1.4.4

Les algorithmes g´
en´
etiques :

Un algorithme g´en´etique GA est un algorithme de recherche locale stochastique qui
emprunte le concept de s´election naturelle des esp`eces pour trouver ainsi les individus les plus
efficaces. Les GA recherchent des solutions optimales, en manipulant des solutions actuelles.
Par exemple, ils combinent des ´el´ements de deux bonnes solutions pour en cr´eer une troisi`eme
qui peut repr´esenter un point tr`es ´eloign´e des solutions parents dans l’espace des solutions.

1.4.5

Les m´
ethodes m´
eta heuristiques :

Ces m´ethodes commencent par une ou bien plusieurs solutions initiales puis utilisent
les strat`eges de recherches. Ces strat`eges essayent d’´eviter des optimums locaux. C’est vrai
qu’elles produisent des solutions de qualit´e mais elles sont couteuses. Ces algorithmes sont
recommand´es pour les probl`emes distribu´es par nature et les probl`emes susceptibles d’´evolution
dynamique.
Voici quelques mod`eles propos´es pour la confection de l’emploi du temps :
1)les m´
ethodes ´
evolutives : l’approche propos´ee est fond´ee sur une programmation par
contraintes en utilisant un algorithme g´en´etique comme moteur d’optimisation.
2)m´
ethodes utilisant la recherche tabou [th0013] : : ici on utilise le codage matriciel M
(i, j) qui contient le nom de la class de professeur i a` la p´eriode j.
Les voisinages propos´es sont :
• Echanger deux cours pour un mˆeme professeur.
• D´eplacer un cours `a une autre p´eriode.
Les r´esultats obtenus avec cette m´ethode ´etaient encourageants.

1.4.6

La m´
ethode mim´
etique :

Les algorithmes mim´etiques sont une hybridation entre les algorithmes de recherche locale et
les algorithmes g´en´etiques. Le principe g´en´eral est le mˆeme que pour les algorithmes g´en´etiques
mis a` part qu’un op´erateur de recherche locale est ajout´e apr`es celui de mutation. La partie
g´en´etique de ces algorithmes peut ˆetre vue comme une forte diversification alors que la partie
recherche locale correspondrait a` une forte intensification (accompagn´ee d’une faible diversification).

Pr´esent´e par : A.M et B.W

UMBB

15

´
CHAPITRE 1. ETAT
DE L’ART

Si un individu v´erifie cette condition, il peut ˆetre ins´er´e dans la population. Dans le cas
contraire, il est d´etruit et une nouvelle g´en´eration est construite. Cette condition est tr`es
importante car elle d´efinit la politique d’´evolution de la population.
Les algorithmes m´em´etiques sont des m´etaheuristiques avanc´ees ; l’id´ee principale de cette
technique est de rendre un algorithme g´en´etique plus efficace par l’ajout d’une recherche locale
en plus de la mutation.
Une des observations g´en´erales provenant de l’impl´ementation d’un algorithme g´en´etique
basique est souvent la faible vitesse de convergence de l’algorithme. L’id´ee de Moscato est donc
d’ajouter une recherche locale qui peut-ˆetre une m´ethode de descente ou une recherche locale
plus ´evolu´ee (recuit simul´e ou recherche tabou).
Il est ´evident que cette simple modification entraine de profonds changements dans le comportement de l’algorithme [th014].

Conclusion :
La confection de l’emploi du temps repr´esente une probl´ematique sur le plan ´economique et
social `a la fois. Sa complexit´e implique de s’appuyer sur une d´emarche scientifique informatis´ee
pour r´ealiser des solutions efficaces. Donc pour avoir un bon planning il faut d´evelopper des
outils bas´es sur des techniques efficaces d’optimisation de ressources tout en respectant les
contraintes pr´ed´efinies et assurer le moindre coˆ
ut possible.
Plusieurs logiciels informatiques ont ´et´e d´evelopp´es afin de r´esoudre le probl`eme de l’emploi
du temps, mais le probl`eme reste toujours pos´e car l’emploi du temps n’est pas standard.
On s’int´eresse au planning dans le domaine p´edagogique o`
u ce processus est tr`es complexe
Pr´esent´e par : A.M et B.W

UMBB

16

´
CHAPITRE 1. ETAT
DE L’ART

car c’est un probl`eme d’optimisation combinatoire tr`es difficile a` r´esoudre : une solution
propos´ee est repr´esent´ee par un ensemble de propri´et´es. L’objectif est d’atteindre la meilleure
combinaison de ces propri´et´es. D’autre part la taille du probl`eme joue un rˆole. Ainsi, dans les
´etablissements ayant un nombre important d’enseignements, il est n´ecessaire de les ordonner
d’une fa¸con concurrente sur trois cot´es : p´eriodes, enseignants et locaux.
Plusieurs approches ont ´et´e propos´ees pour le probl`eme de l’emploi du temps. Les premi`eres
d´emarches de r´esolution de ce probl`eme ´etaient bas´ees sur la th´eorie des graphes, la programmation lin´eaire, mais ces m´ethodes ont prouv´e leurs inad´equations. Donc on a trouv´e
de nouvelles m´ethodes qui s’adaptent mieux pour ce type de probl`eme. Ces m´ethodes se
regroupent principalement parmi les m´etaheuristiques tels que la recherche tabou, le recuit
simul´e, les colonies de fourmis, les algorithmes g´en´etiques et les algorithmes m´em´etiques.

Pr´esent´e par : A.M et B.W

UMBB

2

Approche mim´etique

2.1

Introduction `
a l’algorithme M´
em´
etique (MA) :

L’algorithme m´em´etique qui est une vari´et´e de l’algorithme g´en´etique est une technique
hybride ´evolutionnaire o`
u l’hybridation est r´ealis´ee par l’int´egration de la technique recherche
locale dans l’algorithme g´en´etique. C’est une collaboration entre les deux techniques (la
m´ethode g´en´etique et la recherche locale) :
La premi`ere ´etape consiste `a initialiser un ensemble de solutions al´eatoires. On appelle cet
ensemble la population. La deuxi`eme ´etape s’int´eresse a` choisir deux solutions de la population
d’une fa¸con al´eatoire. Apr`es on va faire un croisement entre eux afin d’obtenir une solution
fils. L’´etape suivante est la mutation qui va ˆetre ex´ecut´ee sur la solution fils obtenue pour faire
quelques modifications avant la derni`ere ´etape appel´ee recherche locale qui consiste a` r´ealiser
une recherche dans le voisinage de la solution consid´er´ee. Si la voisine (s’) est plus efficace et
optimale que (s) alors cette derni`ere va ˆetre remplac´ee par la solution voisine (s’). Ensuite on
va tester si cette solution est plus efficace qu’une autre solution de population, alors la solution
de population va ˆetre remplac´ee par la solution obtenue avec l’algorithme m´em´etique. Sinon
la solution va ˆetre ignor´ee et on va lancer une nouvelle it´eration.

17

´
CHAPITRE 2. APPROCHE MIMETIQUE

18

.
Algorithme mim´
etique ;
Debut
.
POP :=initialiser la populatin () ;
.

ep´
eter
.

ep´
eter
.
{P1, P2} :=choisir al´eatirement deux parent(POP) ;
.
fils :=croisement (P1, P2) ;
.
fils :=mutation (fils) ;
.
fils :=recherceLocale (fils) ;
.
Jusqu’`
a (acceptable (fils)) ;
.
individuRomplacer (POP, fils) ;
.
Jusqu’`
a (satisfaire condition d’arrˆet) ;
Fin

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 2. APPROCHE MIMETIQUE

19

2.2

Explication :

On va partager (d´ecomposer) l’algorithme par des ´etapes : Etape 1 : initialiser la
population avec des valeurs al´eatoire.
Etape 2 : choisir al´eatoirement deux parents P1 et P2 de la population POP.
Etape 3 : faire le croisement des deux parents pour dr´ee un fils.
Etape 4 : faire la mutation sur le fils pour modifier quelque g`ene.
Etape 5 : faire une recherche locale sur le fils pour l’am´eliorer.
Si la solution fils acceptable continue sinon refaire depuis l’´etape 2.
Etape 6 : remplacer le fils dans POP par le plus mauvais individu de population POP
seulement si la qualit´e du fils est meilleure que ce dernier.
G´en´eralement la condition d’arrˆet est de d´efinit par un nombre d’it´eration. [th995]

2.3
2.3.1

Croisement [th997] :
Le croisement `
a un point :

Les ´etapes du croisement a` un point commencent par choisir un nombre entre 1 et la
taille d’un chromosome. Bas´ee sur ce point de croisement les deux chromosomes choisis sont
divis´es en deux parties. Pour cr´eer un seul chromosome fils il va prendre la premi`ere partie du
premier chromosome avant le point de croisement al´eatoire et la deuxi`eme partie du deuxi`eme
chromosome apr`es le point de croisement. [th998]

*****Repr´
esentation sch´
ematique du croisement `
a un seul point*****

2.3.2

Le croisement `
a deux points

Pour le croisement `a deux points on choisit au hasard deux points de croisement. Par la
suite, le chromosome fils va prendre la premi`ere partie du premier chromosome avant le premier
point de croisement al´eatoire et va prendre la deuxi`eme partie du deuxi`eme chromosome apr`es
le premier point de croisement et enfin va prendre la troisi`eme partie du premier chromosome
apr`es le deuxi`eme point de croisement al´eatoire. Cette op´eration est g´en´eralement consid´er´ee
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 2. APPROCHE MIMETIQUE

20
comme plus efficace que la pr´ec´edente.

*****Repr´
esentation sch´
ematique du croisement en 2 points*****

2.4

Mutation :

Nous d´efinissons une mutation comme ´etant de modifier un gˆene dans un chromosome.
Cela revient a` modifier al´eatoirement la valeur d’un param`etre du dispositif. Les mutations
empˆechent l’´evolution de se figer. Elles permettent d’assurer une recherche aussi bien globale que locale, selon le poids et le nombre des valeurs mut´ees. De plus, elles garantissent
math´ematiquement que l’optimum global peut ˆetre atteint.
***** Repr´
esentation sch´
ematique d’une mutation dans un chromosome.*****

Comment r´ealiser notre op´erateur mutation ? De nombreuses m´ethodes existent. Souvent
la probabilit´e de mutation pm par bit et par g´en´eration est fix´ee entre 0,001 et 0,01. On peut
prendre ´egalement pm =1/k o`
u k est le nombre de bits composant un chromosome. Il est possible
d’associer une probabilit´e diff´erente de chaque g`ene. Et ces probabilit´es peuvent ˆetre fixes ou
´evoluer dans le temps. Quelque notion de mutation :

2.4.1

Mutation binaire :

La mutation binaire s’applique a` un seul chromosome. Un bit du chromosome est tir´e au
hasard. Sa valeur est alors invers´ee. Il existe une variante o`
u plusieurs bits peuvent muter au
sein d’un mˆeme chromosome. Un test sous le taux de mutation est effectu´e non plus pour le
chromosome mais pour chacun de ses bits. En cas de succ`es, un nouveau bit tir´e au hasard
remplace l’ancien.

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 2. APPROCHE MIMETIQUE

21

2.4.2

Mutation r´
eelle :

La mutation r´eelle ne se diff´erencie de la mutation binaire que par la nature de l’´el´ement
qu’elle alt`ere. Ce n’est plus un bit qui est invers´e mais une variable r´eelle qui est de nouveau
tir´ee au hasard sur son intervalle de d´efinition.

2.4.3

Mutation non uniforme :

La mutation non uniforme poss`ede la particularit´e de retirer les ´el´ements qu’elle alt`ere
dans un intervalle de d´efinition variable et de plus en plus petit. Plus nous avan¸cons dans les
g´en´erations, moins la mutation n’´ecarte les ´el´ements de la zone de convergence. Cette mutation
adaptative offre un bon ´equilibre entre l’exploration du domaine de recherche et un affinement
des individus. Le coefficient d’att´enuation de l’intervalle est un param`etre de cet op´erateur.

2.5

Recherche locale :

La plus simple fa¸con de repr´esenter la recherche locale est comme suit : imaginer un
alpiniste (escaladeur de montagne) qui est en train de monter une montagne dans un jour
brumeux. Il peut voir la pente du terrain pr`es de lui mais il ne peut pas voir o`
u est le sommet
de la montagne. Donc ses d´ecisions du chemin `a prendre doivent ˆetre reli´ees seulement sur les
informations tir´ees de la pente. L’alpiniste doit choisir une strat´egie pour faire face `a cette
situation et pour une id´ee raisonnable, par exemple, choisir de monter `a chaque pas jusqu’`a
arriver au sommet. Cependant a` cause du brouillard, il ne va jamais ˆetre sˆ
ur si le sommet qu’il
atteint est le sommet r´eel de la montagne ou juste une crˆete du niveau moyen de la montagne.
Interpr´eter cette m´etaphore avec l’optimisation combinatoire. On peut voir la montagne
comme elle a ´et´e d´ecrite par la forme de la fonction objectif. Le choix parmi les actions
possibles pour am´eliorer la fonction objectif doit ˆetre pris par l’examen des solutions locales
proches. Finalement un probl`eme de ce genre de recherche est que g´en´eralement personne
ne peut ˆetre sˆ
ur que la meilleure solution trouv´ee par la recherche locale est actuellement la
meilleure solution globale ou juste soi-disant optimale locale. [th999]

2.5.1

Basic de la recherche locale :

Pour comprendre le basic de la recherche locale on a besoin de d´efinir trois notions :

efinition 1 : l’espace de recherche
Un espace de recherche S a les propri´et´es suivant :
1)Chaque solution s acceptable appartient a` l’espace de recherche s ∈ S.
2)Au moins une solution optimale appartient `a cette espace de recherche.

efinition 2 : le voisinage
On assigne pour chaque solution s ∈ S un voisinage N(s) ⊆ S. le groupe de solution N(s) est
appel´e voisinage de la solution s et chaque ´el´ement s’∈ N(s) et appeler voisin de la solution s.
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 2. APPROCHE MIMETIQUE

22

G´en´eralement chaque solution s’∈ N(s) d´efinie les mouvements possible (ou transition) entre
la solution s et la solution s’ par une modification dans quelque part de la solution s.


efinition 3 : la fonction du coˆ
ut (ou le poids dans un autre ouvrage)
On d´efinit la fonction du coˆ
ut F pour un espace de recherche S qui associer a` chaque ´el´ement
s ∈ S une valeur F(s) qui estimer la qualit´e de la solution.
La fonction du coˆ
ut est utilis´ee pour pousser la recherche vers les bonnes solutions dans
l’espace de recherche, est utilis´ee aussi pour choisir les mouvements `a accomplir `a chaque ´etape
de la recherche.
Pour un probl`eme de recherche la fonction du coˆ
ut F est g´en´eralement bas´ee sur une soi-disant
distance faisable (distance to feasibility), qui compte le nombre de contraintes viol´ees.
Cependant pour les probl`emes d’optimisation, F prend aussi en compte la fonction objective
du probl`eme.

2.6

Algorithme de la recherche locale :

***** Graphe repr´
esente les ´
etapes de la recherche locale*****

Algorithme recherche locale ;

ebut
.
S ← solution initial ;
.

ep´
eter
.
S’← N (solution initial) ;
.
Si (F(S’) meilleur que F(S)) alors
.
S ← S’ ;
.
Fin si ;
.
Jusqu’`
a (condition de fin est satisfaite) ;
Fin

Pr´esent´e par : A.M et B.W

UMBB

23

´
CHAPITRE 2. APPROCHE MIMETIQUE

La proc´edure de la recherche locale qui exploite le voisinage consiste a` (i) d´ebuter avec une
solution initiale s de S et (ii) choisir une solution voisine s’ de N(s) telle que F (s’)<=F(s) puis
a` remplacer s par s’ et r´ep´eter (ii) jusqu’`a ce que pour tout voisin s’ de s, F (s’)<=F (s’).s est
alors un optimum local. [th996]
Conclusion :
L’algorithme m´em´etique repr´esente une hybridation entre la m´ethode g´en´etique et la recherche
locale. Il sert `a modifier les g`enes pour avoir un nouveau chromosome fils avec une qualit´e
meilleure. [th998]

Pr´esent´e par : A.M et B.W

UMBB

3

Description du probl`eme :

Introduction :
Parmi les diff´erents types de probl`emes de l’emploi du temps on s’int´eresse a` celui du
domaine p´edagogique o`
u on va d´ecrire l’aspect g´en´eral de ce dernier, le repr´esenter de diff´erents
angles et montrer les contraintes dures et souples d´ependant de ce probl`eme.

3.1

Aspect G´
en´
erale :

Dans un ´etablissement ´educatif, on dispose d’un ensemble d’´etudiants group´es sous une
structure hi´erarchique (fili`eres, promotions, sections, groupes, etc.). Ils doivent avoir un
ensemble d’enseignements qui se r´ep`etent p´eriodiquement. Chacun de ces enseignements
s’´etend sur une dur´ee de temps, dont l’unit´e ´el´ementaire est la p´eriode.
R´esoudre le probl`eme de l’emploi du temps revient `a affecter a` chacun de ces enseignements un
nombre de p´eriodes cons´ecutives ´egal `a la dur´ee qu’il exige, un local dont le type et la capacit´e
sont convenables et un enseignant apte a` assurer le module concern´e par l’enseignement de
fa¸con a` pr´evenir les conflits entre les enseignants, entre les ´el`eves et sur les locaux.
Le probl`eme de l’emploi du temps se manifeste en diff´erentes formes dont chacune des
formes est sp´ecifique a` l’environnement ou `a l’institution qui en a besoin. Dans notre cas,
le probl`eme de l’emploi du temps ´etudi´e est celui du lyc´ee o`
u les responsables p´edagogiques
ont besoin chaque ann´ee d’´etablir une nouvelle planification des diff´erentes promotions en
essayant au mieux de satisfaire les contraintes ”humaines” des enseignants et des ´el`eves, les
contraintes p´edagogiques impos´ees par la progression des enseignements et en tenant compte
des contraintes ”physiques” li´ees aux ressources mat´erielles ( les locaux, les ´equipements, etc.).
Ce lyc´ee regroupe diff´erentes sp´ecialit´es qui ont un cursus d’enseignement de trois ans qui se
termine par le baccalaur´eat. Le programme p´edagogique de chaque sp´ecialit´e est connu `a priori.
24

`
CHAPITRE 3. DESCRIPTION DU PROBLEME
:

25

Ce programme pr´ecise les mati`eres a` suivre, leurs volumes horaires et quelques informations
p´edagogiques. Selon les besoins p´edagogiques et les conditions physiques des ressources, chaque
formation est structur´ee en promotions, et en groupes. Le nombre d’´el`eves par groupe est
limit´e `a 30 pour pr´eserver un meilleur suivi des ´el`eves. Les enseignants interviennent selon leur
discipline et leur domaine de comp´etence. Administrativement, les enseignants doivent assurer
un nombre minimal d’heures qui est d´efini dans leur statut. Lorsqu’un enseignant est charg´e
d’un enseignement donn´e, il est tenu d’en respecter le volume horaire pr´evu par le responsable
p´edagogique. En cas d’absence, l’enseignant doit pr´evoir des s´eances de rattrapage. Il doit
donc connaˆıtre pr´ecis´ement la disponibilit´e des ressources de sa s´eance. Cette organisation
garantit que tous les ´el`eves qui suivent une mˆeme formation auront eu le mˆeme volume horaire
d’enseignement.
En r´esum´e, les donn´ees du probl`eme `a r´esoudre sont constitu´ees par :
1 ) un ensemble d’horaires disponible sur une semaine de six jours, du samedi au jeudi avec
un nombre de six p´eriodes (on peut le modifier selon nos besoins). La dur´ee d’une p´eriode est
exactement une heure.
2 ) Un ensemble de promotions ou groupes d’´el`eves.
3 ) Un ensemble de sciences d’enseignements a` programmer dans la semaine.
4 ) Un ensemble de locaux (salles et laboratoires).
L’affectation des mati`eres, des enseignants et des locaux `a des p´eriodes est soumise `a
des contraintes qui diff`erent selon leurs priorit´es.
Les contraintes peuvent ˆetre r´eparties en deux grandes classes : les contraintes dures
(absolues) et les contraintes de pr´ef´erences (souples).

3.2

Les contraintes dures :

Ce type de contraintes doit ˆetre obligatoirement satisfait dans toutes les situations car
la violation de l’une de ces contraintes rend l’emploi du temps inefficace dans la r´ealit´e. On
distingue dans notre cas six contraintes dures :
1 ) un enseignant ne peut pas ˆetre affect´e a` deux s´eances diff´erentes a` la mˆeme p´eriode.
2 ) Une salle ne peut pas accueillir deux s´eances diff´erentes `a la mˆeme p´eriode.
3 ) Chaque enseignant doit enseigner une mati`ere qui entre dans ses comp´etences.
4 ) Une mati`ere doit respecter le nombre de s´eances hebdomadaires de cette derni`ere,
c’est-`a-dire si une mati`ere est enseign´ee trois fois par semaine, alors elle doit apparaˆıtre 3 fois
dans le planning de la promotion.
5 ) Un emploi du temps doit comporter toutes les mati`eres d’une promotion.
6 ) Un groupe d’´etudiants ne peut avoir qu’un seul enseignant pour une mati`ere donn´ee, par
exemple il ne peut pas avoir la premi`ere s´eance d’un module avec un enseignant et la prochaine
s´eance du mˆeme module avec un autre enseignant.

Pr´esent´e par : A.M et B.W

UMBB

`
CHAPITRE 3. DESCRIPTION DU PROBLEME
:

26

3.3

Les Contraintes de Pr´
ef´
erence (souples) :

Contrairement au type de contraintes pr´ec´edent, les contraintes de pr´ef´erences n’exigent
pas la v´erification stricte mais d’approcher au maximum de l’objectif voulu. Dans notre cas,
on distingue :
1 ) essayer d’´eviter aux (enseignants ou ´el`eves) des pertes de temps par de trop longs
espacements entre deux s´eances d’une mˆeme journ´ee (pas de trous).
2 ) Eviter que certains jours se trouvent surcharg´es alors que d’autres jours ne sont pas charg´es.
3 ) Les mati`eres de coefficient minimal ne doivent pas occuper les s´eances de la matin´ee d’une
journ´ee donn´ee, au d´etriment des modules de coefficients ´elev´es.
4 ) Minimiser les d´eplacements des ´etudiants dans l’´etablissement.

Conclusion :
La description du probl`eme concern´e peut changer selon les conditions dont on dispose, les
contraintes de pr´ef´erence et les contraintes dures.
L’enseignant peut toujours mettre `a jour le planning dans le but d’am´eliorer le volume des
cours donn´es o`
u bien rattraper quelques s´eances perdues.

Pr´esent´e par : A.M et B.W

UMBB

4

R´esolution et Structures

Dans ce chapitre on va proposer une autre solution pour avoir un programme qui fait des
emplois du temps en appliquant l’algorithme memetique.

4.1

Les structures de donn´
ees utilis´
ees :

Le professeur :constitu´e de deux champs. Le premier c’est le nom du professeur. Le
deuxi`eme champ est l’indice de la mati`ere que le professeur enseigne. Il est `a noter que
chaque enseignant a le droit d’enseigner une seule mati`ere. Cependant il se peut que plusieurs
enseignants enseignent la mˆeme mati`ere. Toutes les informations sur les professeurs vont ˆetre
enregistr´ees dans un tableau nomm´e enseignant.
La mati`
ere : constitu´ee de deux champs. Le premier champ est le nom de la mati`ere
enseign´ee. Le second champ est un entier qui d´efinit le nombre d’heures dont cette mati`ere sera
´etudi´ee par semaine pour chaque groupe. Toutes les mati`eres enseign´ees vont ˆetre enregistr´e
dans un tableau nomm´e curriculum.
L’utilisateur ins`ere les donn´ees qui concernent les professeurs. Les donn´ees qui concernent la
mati`ere seront g´en´er´ees automatiquement.
L’´
ev`
enement : constitu´e de trois champs sont : le professeur (donc on peut connaitre la
mati`ere concern´ee), le num´ero de la salle et l’heure de l’enseignement (timeslot).
Voici la structure d’un ´ev`enement :

27

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

28

On va d´etailler comment g´erer le champ timeslot : L’utilisateur choisit le nombre d’heures
de travail par jour : entre une heure par jour et dix heures par jour. Tous les jours ont le mˆeme
nombre d’heures de travail.
Par exemple : si on a cinq heures de travail par jour et on a six jours par semaine, le tableau
suivant fait correspondre quelques valeurs du timeslot `a l’heure de la semaine concern´ee.

Dans cet exemple le timeslot ne peut pas d´epasser 30. C’est le nombre total d’heures de
travail par semaine.
Les jours de travail par d´efaut sont du dimanche `a jeudi mais l’utilisateur peut modifier le
nombre de jours par semaine et les jours de travail.
Le groupe : est un tableau d’´ev`enements c’est-`a-dire que pour chaque heure d’enseignement
(qui doit appartenir `a l’heure de travail) on affecte l’enseignant, la salle o`
u ce groupe sera affect´e
et un tableau de mˆeme taille de bool´eens. Le but de ce tableau est de connaˆıtre les heures
prises qui sont d´ej`a affect´ees, c’est-`a-dire s’assurer que dans la mˆeme heure le groupe aura un
´ev`enement unique.
Voici la structure d’un groupe :

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

29

Les individus : sont un ensemble de groupes plus deux matrices de bool´eens. La premi`ere
matrice de bool´eens consiste en des lignes qui d´efinissent les heures de travail tandis que les
colonnes d´efinissent les salles de l’´etablissement. Cette matrice assure que dans la mˆeme heure
deux groupes ne peuvent pas ˆetre affect´es `a la mˆeme salle, c’est-`a-dire que la salle sera affect´ee a` un groupe unique dans une heure donn´ee. La deuxi`eme matrice de bool´eens avec les
lignes qui d´efinissent les heures de travail et les colonnes qui d´efinissent les enseignants de cet
´etablissement. Cette matrice assure que dans la mˆeme heure un professeur ne peut pas ˆetre
affect´e `a deux groupes diff´erents, c’est-`a-dire que le professeur s’occupera d’un groupe unique
dans une heure donn´ee.
Voici la structure d’un individu :

4.2

Les contraintes :

Apr`es que l’utilisateur ait d´efini les informations qui concernent les professeurs, les mati`eres
qu’ils enseignent, le nombre d’heures de travail par jour, les jours de travail, le nombre de
salles (par exemple si le nombre de salles est 5, on aura des salles de num´ero 1, 2, 3, 4 et 5)
et le nombre de fois o`
u la mati`ere est enseign´ee a` un groupe par semaine ; on remplira alors
un tableau des professeurs, un autre des mati`eres et on commencera a` g´en´erer un nombre de
solutions initiales d´efinies al´eatoirement et qui seront sauvegard´ees dans un tableau d’individus
nomm´e population. (Chaque individu est suppos´e comme une solution.). Chaque individu
v´erifie obligatoirement les contraintes dures.

4.2.1

Contrainte souple de la solution :

On n’a qu’une seule contrainte souple de la solution. De pr´ef´erence, la solution qui soit
de meilleure qualit´e possible. Mais dans certains cas de manque de ressources, comme par
exemple un nombre insuffisant de professeurs ou de salles ou d’heures de travail par jour ou un
grand nombre de groupes ou d’´ev`enements a` g´erer ; peuvent diminuer la qualit´e de la solution
ou mˆeme rendre la solution impossible.
Ce dernier contient des solutions qui peuvent ˆetres bonnes ou moins bonnes. Deux crit`eres
sont utilis´es pour savoir la qualit´e de la solution qui sont :
• 1er crit`
ere : Le nombre d’heures vides (non enseign´ees) entre deux s´eances de travail
enseign´ees dans le mˆeme jour, de pr´ef´erence sera nul ou une seule heure vide.
• 2`
eme crit`
ere : on doit ´eviter d’enseigner la derni`ere heure du jour.
Voici quelques exemples de jours (on supposera qu’on a sept heures de travail par jour).

Pr´esent´e par : A.M et B.W

UMBB

30

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

On va discuter maintenant de la qualit´e des emplois du temps ci-dessus et comment elle
est calcul´ee.
On d´efinit une variable (poids) qui d´epend des deux crit`eres pr´ec´edents. Ce tableau explique
comment est calcul´e le poids.

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

31

Le poids final c’est le poids de l’individu qui est la somme de tous les poids de tous les
groupes qui le constituent (le poids du groupe est calcul´e avec l’accumulation des poids de
chaque jour d’´etude).

4.2.2

Contraintes dures de la solution :

On a cinq contraintes dures que la solution doit imp´erativement v´erifier. L’absence de l’une
de ces contraintes implique la non existence de la solution. Ces contraintes sont :
1. Pour chaque groupe, une mati`ere doit ˆetre enseign´ee par un et un seul professeur. Bien qu’il
soit possible que plusieurs enseignants enseignent la mˆeme mati`ere.
2. Pour chaque heure de travail enseign´ee, on assure qu’un groupe a un seul ´ev`enement ou
aucun ´ev`enement a` la fois mais pas deux ´ev`enements ou plus dans une mˆeme heure.
3. Pour chaque heure de travail enseign´ee, on assure qu’une salle soit occup´ee par un seul
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

32

groupe ou qu’elle soit vide, mais deux groupes ne peuvent pas ˆetre affect´es `a une mˆeme salle
dans le mˆeme groupe.
4. Pour chaque heure de travail enseign´e, un professeur ne peut pas ˆetre affect´e `a deux
groupes diff´erents, il peut ˆetre affect´e a` un groupe, ou aucun groupe mais pas deux groupes
simultan´ement.
5. Chaque mati`ere doit ˆetre enseign´ee un nombre de fois d´ej`a d´efini initialement par l’utilisateur
pour chaque groupe. C’est-`a-dire le groupe ne peut pas d´epasser ou diminuer le nombre de fois
qu’une mati`ere doit ˆetre enseign´ee. Par exemple : si la mati`ere sciences doit ˆetre enseign´ee 5
fois par semaine, la solution doit donc v´erifier cette contrainte.

4.3
4.3.1

L’algorithme memetique :
Cr´
eation de la population initiale :

Pour cr´eer la population initiale qui est un ensemble d’individus v´erifiant les cinq contraintes
dures, il faut d’abord cr´eer des ´ev`enements qui constituent un groupe. Dans cette ´etape on
v´erifie deux contraintes parmi les Cinq contraintes dures qui sont : la contrainte num´ero (2) et
la contrainte num´ero (3), on cr´ee autant de groupes que l’utilisateur a choisi pour construire
un individu en v´erifiant les trois autres contraintes dures. Cet individu est une solution initiale.
De la mˆeme fa¸con on cr´ee un nombre pr´ed´efini d’individus ce qu’on appelle la population
initiale et on sauvegarde dans le tableau population.
Voici l’algorithme de la cr´eation de la population initiale.

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

33

4.4

Croisement :

La technique du croisement consiste `a choisir deux individus distincts al´eatoirement `a
partir de la population initiale. Soit un nombre (n) al´eatoire tel que 1≤n< nombre de groupes.
A partir de ces deux individus on cr´ee un nouveau individu dont ses (n) premiers groupes sont
les (n) premiers groupes du premier individu et les autres groupes restant sont les groupes du
deuxi`eme individu a` partir du groupe num´ero (n+1).
Exemple : supposons deux individus constitu´es de sept groupes, donc le (n) doit v´erifier : 1≤n<7

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

34

En cr´eant cet individu, les contraintes dures de num´ero (1), (2) et (5) sont automatiquement
v´erifi´ees, par contre les deux contraintes restantes de num´ero (3) et (4) c’est-`a-dire pour chaque
´ev`enement on v´erifie si la classe occup´ee ´etait vide et si l’enseignant charg´ee de cet ´ev`enement
n’est pas occup´e avec un autre groupe. Si les deux contraintes sont v´erifi´ees, le croisement est
effectu´e avec succ`es. Sinon si l’une de ces contraintes n’est pas v´erifi´ee on refait la proc´edure
de croisement d`es le d´ebut. C’est-`a-dire choisir deux autres individus de la population initiale
et ainsi de suite. Le but de refaire toute la proc´edure et ne pas recommencer a` r´eg´en´erer
le nombre (n) al´eatoirement c’est d’´eviter ainsi la boucle infinie, car dans certains cas deux
individus ne peuvent pas g´en´erer un nouvel individu v´erifiant les contraintes dures quel que
soit le nombre (n).
Voici l’algorithme de croisement :
Algorithme croisement ;
Procedure croisement () : individu
Debut
.
Var Contraint durs accepter : bool´een ; .
Var P1, P2, n : entier ;
.
Var child : individu ;
.
R´ep´eter
.
Choisir parent (population, P1, P2) ;
.
n=point croisement (nbr groupe) ;
.
Initialiser individue (child) ;
.
Contraint durs accepter :=true ;
.
Pour i de 0 a` nbr groupe faire
.
Debut
.
Si i ¡ n alors faire
.
Debut
.
Contraint durs accepter :=Copier groupe (i, child, P1) ;
.
Sinon
.
Contraint durs accepter :=Copier groupe (i, child, P2) ;
.
Fin si ;
.
Jusqu’`a (contrain durs accepter == true) ;
Fin ;

4.5

Mutation :

Apr`es avoir effectu´e un croisement, on aura comme r´esultat un individu sur qui on effectuera
la mutation.
On a expliqu´e ci-dessus que la qualit´e de la solution d´epend de la distribution des heures de
travail enseign´ees dans l’emploi du temps, c’est pour cela que dans la mutation on joue sur le
champ heure (timeslot) dans chaque ´ev`enement de l’individu.
La probabilit´e (P) d’effectuer un changement de l’heure pour un ´ev`enement est l’inverse du
nombre d’´ev`enements par individu. Rappelons que l’individu est constitu´e d’un certain nombre
Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

35

de groupes et chaque groupe constitu´e d’un nombre fixe d’´ev`enements.

Si pour cet ´ev`enement r ≤ P, on lib`ere l’heure de cet ´ev`enement (timeslot), c’est-`a-dire
que cette heure devient une heure libre pour le groupe et le professeur qui enseigne ce groupe
et la salle qui ´et´e occup´ee seront libres `a ce moment. Ensuite on cherche al´eatoirement parmi
les heures libres du groupe une nouvelle heure pour remplacer l’ancienne. En d’autres mots
changer l’horaire de l’´ev`enement enseign´e sachant que la salle occup´ee est la mˆeme et la mati`ere
enseign´ee est la mˆeme et sera enseign´ee par le mˆeme professeur sans oublier de mettre a` jour
notre tableau et matrices de boolien.
Si r > P, on ne change rien et on passe a` l’´ev`enement suivant.
Voici l’algorithme de la mutation :
Algorithme mutation ;
Procedure mutation (individu S)
Debut
.
Var P, r : r´eel ;
.
Var nouveau, ancien : entier ;
.
P :=1/ (nbr groupe * nbr event) ;
.
Pour i de 0 `a nbr groupe faire
.
Debut
.
Pour j=0 `a nbr event faire
.
Debut
.
r :=valeur aleatoire () ;
.
Si r ≤ P alors faire
.
Debut
.
Affecter nouvelle heur (child,i,j) ;
.
Fin si ;
.
Fin pour ;
.
Fin pour ;
Fin ;

4.6

La recherche locale :

A partir de l’individu r´esultant de la mutation qu’on appelle individu mutated , on
cr´ee des copies de cet individu et on change seulement une seule heure d’enseignement (timeslot) dans un seul ´ev`enement dans l’individu copi´e.
Pr´esent´e par : A.M et B.W

UMBB

36

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

Pour le mˆeme ´ev`enement on remplace l’heure d’enseignement par toutes les heures de travail
possibles et on v´erifie a` chaque fois les contraintes dures. Si elles sont v´erifi´ees, le nouvel individu
qui est une copie de individu mutated avec un seul changement d’heure d’enseignement
dans un seul ´ev`enement parmi tous les ´ev`enements de l’individu, il sera sauvegard´e dans un
tableau d’individus, sinon il sera rejet´e.
On fait la mˆeme proc´edure pour chaque ´ev`enement de individu mutated . On aura comme
r´esultat un tableau des individus voisins a` individu mutated . Le nombre d’individus
r´esultant qu’on appelle individus voisins est ´egale au nombre total d’´ev`enements dans
l’individu multipli´e fois le nombre d’heures (timeslot) de travail dans la semaine.
La derni`ere ´etape de la recherche locale consista `a choisir parmi tous les individus voisins celui
qui a le poids le plus faible, c’est-`a-dire la qualit´e la plus bonne. Si son poids est plus faible
que le poids de individu mutated r´esultant de la mutation donc on le remplace, sinon on
garde l’individu r´esultant de la mutation.
Voici l’algorithme de la recherche locale :
Algorithme recherche locale ;
Constant MAX NEIGHBOUR : = ... ;
Var voisins [MAX NEIGHBOUR] : individu ;
Procedure recherche local (individu S)
D´ebut
.
Var nbr voisin, poids voisin, poids solution : entier ;
.
Var S’ : individu ;
.
nbr voisin :=voisinage (S) ; /* cr´eer le voisinage de
.
la solution et retourne le nombre devoisins cr´ees */
.
poids solution := poids individu(S) ;
.
Pour i = 0 `a nbr voisin faire
.
D´ebut
.
poids voisin := poids individu (voisins[i]) ;
.
/* La fonction poids individu calcule le poids de l’individu
.
c’est pour connaitre la meilleuresolution.*/
.
Si poids voisin ¡ poids solution alors faire
.
D´ebut
.
S=S’ ;
.
poids solution := poids voisin ;
.
Fin si ;
.
Fin pour ;
Fin ;
Apr`es la recherche locale on prend parmi la population, l’individu ayant le poids le plus haut
et on le compare avec le poids de l’individu r´esultant de la recherche locale. Si ce dernier est
de meilleure qualit´e on le remplace dans la population, sinon on ne change rien.
On refait les proc´edures de croisement, mutation et la recherche locale un nombre d´efini de fois
pour am´eliorer la qualit´e des individus dans le tableau de la population.
A la fin on choisit l’individu ayant le poids le plus faible, c’est-`a-dire l’individu de qualit´e
meilleure. C’est la solution propos´ee.
Pr´esent´e par : A.M et B.W

UMBB

37

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

La recherche des solutions par l’algorithme mim´etique est comme suit :
Algorithme memetique ; Constant ITERATION :=... ;
Constant MAX POPULATION :=... ;
Var population [MAX POPULATION] : individu ;
Debut
.
Var i, worst : entier ;
.
Var P1, P2, S : individu ;
.
creation population initial () ;
.
Pour i := 0 `a ITERATION faire
.
Debut
.
S : =croisement (P1, P2) ;
.
mutation (S) ;
.
recherche locale(S) ;
.
// Chercher le plus mauvais individu dans la population.
.
worst :=indiceWorstIndividu () ;
.
/* Remplacer se dernier par la solution S si le poids de S est inferieur a lui.*/
.
Si (poidsIndividu(S) ¡ poidsIndividu (population [worst])) alors faire
.
population [worst] :=S ;
.
Fin Si ;
.
Fin pour ;
Fin ;
Explication :
Au d´ebut on fait :
Etape 1 : cr´eer la population initiale avec chaque individu qui v´erifie les contraintes dures.
L’individu a une valeur al´eatoire.
Ensuite, pour chaque it´eration on fait :
Etape 2 : appliquer la fonction de croisement sur deux parents choisis al´eatoirement `a partir
de la population et faire le croisement entre ses deux parents. On obtient comme r´esultat un
fils S qui est compos´e de groupes du premier parent et compos´e aussi d’autres groupes du
deuxi`eme parent.
Etape 3 : on applique l’op´eration mutation sur le fils S pour modifier un ou plusieur(s)
´ev`enement(s) ou aucun ´ev`enement.
Etape 4 : appliquer la fonction recherche locale sur la solution S pour ´eventuellement
remplacer cette solution par la meilleure solution qui se trouve dans son voisinage.
Remarque : les fonctions croisement, mutation et recherche locale v´erifient les contraintes
dures au moment de la g´en´eration des solutions.
Etape 5 : Chercher le plus mauvais individu dans la population et le remplacer par la solution
S si elle est meilleure.
On r´ep`ete les ´etapes (2), (3), (4) et (5) un nombre d’it´eration d´efini au pr´ealable.

Pr´esent´e par : A.M et B.W

UMBB

38

´
CHAPITRE 4. RESOLUTION
ET STRUCTURES

Conclusion :
La partie de production, la repr´esentation des structures, la mani`ere par laquelle on
mod´elise notre emploi du temps et les coh´erences entre les fonctions d’un tel algorithme sont
des taches `a respecter.
Toujours essayer au maximum d’assurer le bon ordonnancement et la coordination entre les
diff´erentes parties de notre algorithme car les meilleurs r´esultats ne peuvent ˆetre obtenus
seulement si toutes les partie d’un algorithme sont bien ordonn´ees et bien rang´ees.

Pr´esent´e par : A.M et B.W

UMBB

5

Impl´ementation

L’objectif de notre travail est de trouver la meilleure solution qui soit efficace et qui r´eponde
aux besoins de l’utilisateur. L’application doit avoir un temps de r´eponse optimale.

5.1

Les outils utilis´
es dans la r´
ealisation de cette application :

L’outil utilis´e pour d´evelopper cette application est l’environnement de d´eveloppement
int´egr´e Qt creator (langage C++) avec un syst`eme d’exploitation Windows 7.

5.2

Pr´
esentation de l’application :

On prend un ´echantillon de l’application pour bien d´ecrire son utilisation. Apr`es l’ex´ecution
de l’application, la fenˆetre principale apparaitra comme suit :

39

40

´
CHAPITRE 5. IMPLEMENTATION

Il y a trois ensembles d’entr´ees qui apparaissent ici :
1- L’ensemble (1) encadr´e avec le jaune repr´esente les donn´ees qui doivent ˆetre introduites par
l’utilisateur.
2- L’ensemble (2) encadr´e avec le vert repr´esente le nombre d’it´erations (bas → 500 it´erations,
moyen → 2500 it´erations, haut → 5000 it´erations).
3- L’ensemble (3) encadr´e avec le rouge permet de choisir d’importer les donn´ees en utilisant la
zone au-dessous ou bien de les saisir manuellement. Les donn´ees saisies manuellement peuvent
ˆetre sauvegard´ees dans des fichiers par le bouton de sauvegarde dans la barre d’outils.

Une fois que l’utilisateur a introduit le nombre d’enseignants dans le programme, deux
nouveaux ensembles vont ˆetre affich´es :

Pr´esent´e par : A.M et B.W

UMBB

´
CHAPITRE 5. IMPLEMENTATION

41

1- L’ensemble (1) encadr´e en rouge repr´esente l’ensemble des enseignants et la mati`ere
enseign´ee par chacun.
2- L’ensemble (2) encadr´e en vert repr´esente le nombre de s´eances hebdomadaires de chaque
mati`ere ´etudi´ee par chaque groupe.
Remarque : l’ensemble 2 peut ˆetre affich´e seulement si toutes les informations des
enseignants (ensemble 1) sont donn´ees.
Apr`es l’introduction de toutes les informations n´ecessaires, on peut ensuite lancer la
r´esolution du probl`eme.
Le r´esultat obtenu va ˆetre comme suit :
Remarque : Le r´esultat est affich´e sur une nouvelle fenˆetre. Pour voir tout le tableau du
r´esultat il faut d´eplacer l’ascenseur gauche.
Le bouton Enregistrer sert a` sauvegarder le r´esultat dans un fichier Excel de type ”*.csv”.

Voici le reste du r´esultat du test :

Pr´esent´e par : A.M et B.W

UMBB

42

Pr´esent´e par : A.M et B.W

´
CHAPITRE 5. IMPLEMENTATION

UMBB

43

´
CHAPITRE 5. IMPLEMENTATION

On remarque que toutes les contraintes dures mentionn´ees au chapitre (4) sont satisfaites.
Le temps de calcule se change en fonction de nombre d’it´erations, et en fonction de la taille de
donn´ees. Apr`es les tests d’application on a trouv´es les r´esultats suivants :

Remarque :en ce qui concerne la taille de donn´ees, on joue sur le nombre de groupes.

Pr´esent´e par : A.M et B.W

UMBB

44

´
CHAPITRE 5. IMPLEMENTATION

Conclusion :
L’utilisation de l’environnement de d´eveloppement int´egr´e Qt creator permet d’offrir une
bonne interface graphique qui facilite la communication entre l’utilisateur et l’application.
Cela permet d’assurer une bonne coh´erence entre la machine et l’utilisateur.
On peut am´eliorer notre programme en ajoutant quelques fonctionnalit´es comme :
1) Permettre a` certaines mati`eres d’ˆetre enseign´ees non pas une heure seulement mais pendant
deux ou trois heures d’affil´ee, telle que l’´education physique (sport) a` laquelle est consacr´ee
g´en´eralement deux heures de temps.
2) Permettre aux enseignants la possibilit´e d’enseigner plusieurs mati`eres.
3) Permettre de choisir les heures de travail, les heures de repos et les heures de r´ecr´eation.
4) Les groupes peuvent ˆetre de diff´erentes fili`eres (Maths, Sciences, Lettres, etc.) et de diff´erents
niveaux d’´etudes (premi`ere, deuxi`eme ann´ee, etc.).

Pr´esent´e par : A.M et B.W

UMBB

Conclusion g´en´erale :

L’objectif de ce m´emoire est la r´esolution du probl`eme de l’emploi du temps dans le secteur
de l’enseignement `a l’aide de l’algorithme mim´etique.

On a fait une conception d´etaill´e de ce probl`eme, on a introduit quelques d´efinitions
introductives, et on a cit´e des m´ethodes internes pour r´esoudre ce probl`eme, apr`es on a ´etudi´e
la m´ethode mim´etique pour trouver des solutions acceptables, fiables et efficaces.

L’´elaboration de ce travail n´ecessite une bonne conception des besoins des utilisateurs. Un
emploi du temps est dit efficace dans un seul cas. C’est lorsque toutes les contraintes dures
sont v´erifi´ees. En ce qui concerne les contraintes de pr´ef´erences, elles doivent ˆetre optimis´ees
au maximum.
Le temps d’ex´ecution d´epend de deux variantes :
- le nombre d’it´erations.
- la taille des donn´ees introduites.

Le temps sera augment´e a` chaque fois qu’on augmentera les valeurs de ces deux variantes.

Notre travail peut ˆetre d´evelopp´e de diff´erents et de plusieurs cot´es afin de former une
application plus avanc´ee. On peut faire des modifications pour r´eduire le temps de r´eponse, et
pour le rendre prˆet a` utiliser dans les universit´es.

45

References bibliographiques :

[th001] : ] : Schaerf A., ET Schaerf M. ”Local search techniques for large high school
timetabling”, in proceeding of the 1st international conferenceon the practice and theory of
automated timetabling, pp. 313-323, 1995.
[th003] : CHAN Yew Cheong, Peter ¡¡La planification du personnel : acteurs, actions et termes
multiples pour une planification op´erationnelle des personnes¿¿, l’UNIVERSITE JOSEPH
FOURIER - Grenoble 1, 22 Octobre 2002.
´
[th002] : R´emy-Robert, Alexandre JOSEPH ¡¡ Syst`emes Interactifs d’Aide `a l’Elaboration
de Plannings de Travail de Personnel¿¿, UNIVERSITE´ JOSEPH FOURIER-GRENOBLE I
´
SCIENCES and GEOGRAPHIE,
07 novembre 2003.
[th004] : Sandhu k., ”Automating class schedule generation in the context of university
timetabling information system”, School of Management, Nathan Campus, Griffith University,
21 September 2001.
[th005] : Yann le Fablec, ”pr´evision de trajectoires d’avions par r´eseaux de neurones”, Th`ese,
Laboratoire d’optimisation globale CENA/ENAC, Toulouse, 1999.
[th006] : De Werra D., ”An Introduction to Timetabling”, European Journal of Operational
research 19, 151-162.1985.
[th007] : Georges Weil, Kamel Heus, Patrice Fran¸cois, ”Gymnaste : Aide `a l’´elaboration des
roulements infirmiers. Du traitement des absences au management participatif”, Laboratoire
TIMC, SILM, CHU de Grenoble, Universit´e Joseph Fourier- Grenoble, 1994.
[th008] :Edmund Kieran Burke et Sanja Petrovic, ” Recent Research Directions in Automated
Timetabling”, ASAP Research Group, school of computer science and information technology,
108 university of Nottingham, EJOR, 2002.
[th009] : Krzysztof Socha, Joshua Knowles and Michael Sampels, ”A MAX-MIN Ant System
for the University Course Timetabling Problem”, IRIDIA, Universit´e libre de Bruxelles, 2002.
[th0010] : G. Pesant, P. Galinier, ”un mod`ele de programmation par contraintes pour la
confection d’horaires d’infirmi`eres”, European Journal of Operational Research, 234 :156167,2000.
[th0011] : G. Cangini, ”une m´ethode hybride pour la confection d’horaires de m´edecins pour
l’hˆopital Cˆote-des Neiges”, M´emoire de maˆıtrise, CRT, GERAD et Ecole Polytechnique de
Montr´eal, D´epartement de G´enie Electrique et de G´enie Informatique, 2002.
[th0012] : Daumas Authman ET associ´es, ”j’Road Planner”.
[th0013] : ] : Schaerf A., ”Tabu Search technique for large high school timetabling problems”,
In Proceeding of the 13th national conference on artificial intelligence,USA,1996.
[th0014] : Fr´ed´eric LARDEUX Devant le ’Approches Hybrides pour les probl`emes de
satisfiabilit´e (SAT et MAX-SAT)’. 25 Novembre 2005.

46

47

´
CHAPITRE 5. IMPLEMENTATION

[th0015] : Le temps de travail a` l’hˆopital LE BLOG DES HOSPITALIERS F.O SANTE.
13 juin 2011.
[th0016] : cours complexit´e, Deug-Mias-2 Institut Galil´ee.
[th0017] : Complexit´e. PDF document
[th0018] : ] : Complexit´e des algorithmes http// : Complexit´e des algorithmes.htm.
[th997] :http ://produ.chez.com/badro/
[th998] : Gabriella Budai, Rommert Dekker, Uzay Kaymak ”Genetic and mimetic algorithms
for scheduling railway maintenance activities”.
[th999] : Luca Di Gaspero ”Local Search Techniques for Scheduling Problems : Algorithms
and Software Tools”.
[th996] : Marie ?l´eonore Marmion ”Recherche locale et optimisation combinatoire : De
l’analyse structurelle d’un probl`eme la conception d’algorithmes efficaces”
[th666] : P (complexit´e) - Wikip´edia.
[th995] : Daniel Cosmi ”Algorithmes Heuristiques et Techniques d’Apprentissage Applications
au Probl`eme de Coloration de Graphe”.

Pr´esent´e par : A.M et B.W

UMBB



Documents similaires


tp n7
gbi30uj
solutions de viscosite et programmation dynamique 14 1
orfwmt8
cours algorithmique
1 markowitz