Soutenance mémoire
Modélisation mathématique pour la création des emploi du temps
Introduction
La création des emplois du temps, répondant à un certain nombre de critères et de contraintes, exige une modélisation mathématique. Cette modélisation nécessite la définition d’un certain nombre de variables, la traduction des contraintes, et les critères des emplois du temps, par exemple le fait qu’ils doivent être libres d’heures creuses, seront ex-primés dans la fonction objectif.
Au début de ce chapitre, nous expliquons le choix des variables et la fonction objectif, puis nous traduisons les contraintes à des équa-tions mathématiques, afin de donner un modèle mathématique.
Modélisation
Modéliser un problème consiste à le rendre sous forme d’un en-semble d’équations mathématiques. Et déterminer
– Les variables (inconnues)
– Les contraintes
– L’objectif à atteindre (optimisation)
Les paramètres
Le nombre de matières allant de 1 jusqu’à NM
G le nombre de groupes allant de 1 jusqu’à NG
C le nombre de créneaux allant de 1 jusqu’à NC
le nombre de salles générales
∶ le nombre de salles spéciales pour la matière i le nombre d’heure hebdomadaire pour la classe j
∀ j=1,………NG
le nombre d’heure hebdomadaire de la matière i pour la classe j
∀ =1,…,NG,∀ =1,…,
le nombre d’enseignants de la matière i
∀ =1,…,
Les variables
On définit des variables qui dépendent à la fois de la matière, du groupe et du créneau
Si un groupe j a une séance d’une matière i pendant un créneau k
Xijk = 0 sinon
Il s’agit de variables binaires n’ayant que deux valeurs possibles 0 ou 1.
Les contraintes
Dans ce problème nous disposons de plusieurs contraintes con-traintes de disponibilité, contraintes de respect de nombre d’heures exigées, contrainte des matières.
On commence par
La disponibilité des salles
Pour les matières qui peuvent se dérouler dans les salles géné-rales le total des salles générales réservées pendant un créneau k, ne doit pas dépasser le nombre de salles générales disponibles dans le collège.
∑ ∑ ∀ k = {1,……… NC}
Explication
Pour chaque créneau, on vérifie que la somme de toutes les séances qui auront lieu dans des salles générales est inférieure ou égale au nombre de salles disponibles. Alors, la somme sur tous les groupes égale le nombre de séances qui se déroulent pendant un créneau k.
Et pour les matières qui ont des salles spéciales, Nous écrivons
∑ ∀ k = {1,……… NC}
∀ i une matière à des salles spéciales.
Le nombre d’heures hebdomadaires
Il faut que le nombre d’heures de chaque matière pour un groupe dans les emplois du temps soit égal au nombre d’heures exigé dans les données
La charge d’une matière
∀ i = {1,……… NM}
∀ j = {1,……… NG}
Un élève ne doit pas étudier plus de deux heures d’une matière par jour. Pour cela, nous avons testé tous les jours, il faut que la somme sur les créneaux de chaque jour soit inférieure ou égale à 2, pour chaque matière i et chaque groupe j.
Les créneaux de l’enseignement dans l’établissement scolaire sont répartis sur les jours de la manière suivante
– Indépendance des matières
Un élève ne peut pas assister à plus d’un cours à la fois, c.à.d.
étudier plus d’une matière pendant un créneau k.
La fonction objectif
Notre but est de réduire le nombre d’heures creuses c’est-à-dire rendre la somme de la différence entre deux créneaux successifs petit autant que possible pour tous les groupes, alors nous écrivons
Pour ‡ {4, 8, 12, 16, 20, 24, 28, 32, 36,40}
Puisque,
Alors,
Cette formule représente la différence entre deux créneaux suc-cessifs.
Donc la somme sur tous les créneaux donne la somme des différences pour le groupe j pendant toute la semaine
Et pour éviter les différences soit entre les créneaux de 12h et 14h, ou entre les créneaux de 18h et 8h du lendemain nous supposons que
‡ {4, 8, 12, 16, 20, 24, 28, 32, 36,40}
Le modèle mathématique
Nous proposons un modèle mathématique dont la fonction objectif est de minimiser le nombre d’heures creuses en prenant en considération l’ensemble des contraintes, de disponibilité de salles, de disponibilité d’enseignants,…etc.
|
Table des matières
Introduction Générale
Chapitre I Présentation du problème des emplois du temps
Introduction
1- Présentation du collège Sidi Boumediene
2- Vocabulaire
3- Les données du collège
4- La vérification de la suffisance des enseignants et de salles
4.1-La vérification du nombre nécessaire d’enseignants
4.2-La vérification du nombre d’heures de travail de chaque enseignant
4.3- La vérification du nombre des salles
5- Description des contraintes
Conclusion
Chapitre II Modélisation mathématique pour la création des emploi du temps
Introduction
1- Modélisation
1.1-Les paramètres
1.2- Les variables
1.3- Les contraintes
a- La disponibilité des salles
b- Le nombre d’heures hebdomadaire
c- La charge d’une matière
d- L’indépendance des matières
1.4- La fonction objectif
1.5- Le module mathématique
Conclusion
Chapitre III La résolution du problème par l’algorithme génétique
Introduction
1- L’algorithme génétique
1.1-Pourquoi l’algorithme génétique
1.2- Vocabulaires
2- Fonctionnement des algorithmes génétiques
2.1- Codage
2.2- La Sélection
2.3 – Le Croisement
2.4 – La Mutation
3- Processus de résolution l’algorithme génétique de Matlab
3.1- Préparation des arguments de GA
3.2- Présentation des variables
3.3- Paramètres de GA solver
Conclusion
Conclusion générale
Références
Télécharger le rapport complet
