Gestion Des Emplois Du Temps

1

Introduction gnrale

Les rformes pdagogiques dans les diffrentes universits mondiales en gnral et dans

les universits marocaines en particulier confrontent des problmes majeurs au niveau de la

gestion des emplois du temps des examens.

Les deux problmes essentiels qui se posent sont :

1) Un tudiant inscrit dans deux modules diffrents a le droit de passer les deux

examens, comment donc organiser ces deux examens de tel sorte quils ne se

passent pas en mme temps ?

2) Pour des raisons pdagogiques comment loigner le maximum possible entre deux

examens qui ont des tudiants en commun ?

Lobjectif de ce mmoire est de rpondre la premire question et ceci en utilisant la

mthode de la coloration des graphes.

Le mmoire est organis en trois chapitres :

Dans le premier chapitre, nous introduisons les notions prliminaires lies la thorie des

graphes et loptimisation combinatoire.

Nous abordons dans le deuxime chapitre le problme de coloration de graphe, et nous

essayons de trouver lensemble indpendant maximal (MIS), nous proposons une approche

de rsolution pour ce problme base sur une relaxation de la contrainte surrogate.

Le quatrime chapitre de ce mmoire prsente une application de la coloration de graphe

au problme de cration des horaires dexamen, nous tudions lorganisation des examens

dans un semestre la FST de Fs.

Et nous terminons par une conclusion.

2

Chapitre 1

Thorie de graphe et optimisation combinatoire

1.1 -Introduction

La thorie des graphes prsente un domaine des mathmatiques qui permet de

rsoudre efficacement une grande varit de problmes pratiques en les ramenant des

configurations simples laide de points et de liaisons entre ces points. Elle est aussi lun

des instruments les plus courants et les plus pertinents pour rsoudre des problmes

discrets de la recherche oprationnelle (RO).

Plusieurs problmes de diffrents domaines peuvent tre modliss sous forme dun graphe

Diffrentes tches excutes par une mnagre lors de la prparation dun djeuner ;

Trafic routier ;

Expdition du ptrole brut depuis les rgions productrice jusqu la raffinerie des

rgions

consommatrices ;

Rseaux de voies ferres ;

Fils de tlphone ;

Distribution de marchandises (voyageur de commerce)

Chimie : Modlisation de structures de molcules.

1.2 Gnralits sur les graphes

La thorie des graphes est ne en 1736 quand Euler dmontra quil tait impossible de

traverser chacun des sept ponts de la ville de Knigsberg (Kaliningrad) une fois

exactement et de revenir au point de dpart.

3

Le graphe des sept ponts de la ville de Knigsberg

1.2.1 Dfinitions et terminologie

Dfinition dun graphe :

Un graphe G est constitu de deux ensembles :

- Un ensemble X de points appels sommets

- Un ensemble U de lignes reliant chacune deux sommets

On note un graphe par G = (X, U). Pour tout (x, y) X ou x, y U, x est dite extrmit

initiale et y extrmit finale. Le nombre de sommets est appel ordre du graphe.

Exemples de graphe

toile anneau

4

Graphe orient

Un graphe est dit orient, ou bien direct, est un graphe dont on peut distinguer entre les

liens (x, y) et (y, x), cest--dire (x, y) (y, x), et on appelle le lien un arc.

y est un successeur de x tandis que x est un prdcesseur de y

A B

D C

F

Graphe non orient

Un graphe est dit non orient ou bien indirect si la prcision de sens de lien (x,y) et la

Distinction entre extrmit initiale et extrmit terminale ne jouent aucun rle. Tout lment

(x, y) E est une arte.

B C

A D

E

Remarque

- Tout graphe orient peut tre transform en un graphe non orient en supprimant

lorientation des arcs.

- Tout graphe non orient peut tre transform en un graphe orient en remplaant

chaque arte par deux arcs en sens inverse.

On note un arc par (A, B) ou AB

5

A B A B

Soit X = {x1, x2,.. xn} un ensemble de sommets.

On peut dfinir un graphe par la relation binaire R : xi R xj (xi, xj) est un arc du

graphe.

Dfinition

Si xi R xj , on dit que les sommets xi et xj sont adjacents.

Dfinition quivalente

xi et xj sont adjacents sil y a un arc qui les relis.

1.2.2 Reprsentation dun graphe

Un graphe peut avoir plusieurs reprsentations, nous utilisons dans ce mmoire la

reprsentation matricielle

1.2.2.1 Matrice dadjacence

Les outils classiques dalgbre linaire peuvent galement tre utiliss pour coder les

graphes. La premire ide consiste considrer chaque arc comme un lien entre deux

sommets.

Dfinition :

Considrons un graphe G = (X, A) comportant n sommets. La matrice dadjacence de G est

gale la matrice U = (uij) de dimension n n telle que :

uij = 1 (, ) ( (, ) )0

Une telle matrice, ne contenant que des 0 et des 1 est appele, de manire gnrale,

une matrice boolenne.

6

Un graphe orient quelconque a une matrice dadjacence quelconque, alors quun graphe

non orient possde une matrice dadjacence symtrique. Labsence de boucle se traduit

par une diagonale nulle.

Exemple

Considrons le graphe suivant :

1 5

4

2

3

La matrice dadjacence du graphe est la suivante :

M =

0 1 1 1 10 0 1 0 00 0 0 1 00 0 0 0 01 0 0 1 0

1.2.2.2 Matrice dincidence

La seconde ide permettant une reprsentation matricielle dun graphe exploite la relation

dincidence entre artes et sommets.

Dfinition : Considrons un graphe oriente sans boucle G = (X, A) comportant n

sommets x1, . . . , xn et m artes a1, . . . , am. On appelle matrice dincidence (aux arcs) de G

la matrice M = (mij) de dimension n m telle que :

7

1 si xi est lextrmit initiale de ai

mij = 1 si xi est lextrmit terminale de aj

0 si xi nest pas une extrmit de aj

Pour un graphe non oriente sans boucle, la matrice dincidence (aux artes) est dfinie par

:

= 1 si xi est une extrmit de aj0

La matrice dincidence du graphe de la figure 6 secrit sous la forme suivante :

M =

1 0 1 0 1 1 1 01 1 0 0 0 0 0 00 1 1 1 0 0 0 00 0 0 1 1 0 0 10 0 0 0 0 1 1 1

1.3 Loptimisation combinatoire

Loptimisation combinatoire occupe une place trs importante en recherche

oprationnelle et en informatique. De nombreuses applications pouvant tre modlises

sous la forme dun problme doptimisation combinatoire telles que le problme du

voyageur de commerce, lordonnancement de tches, le problme de la coloration de

graphe, etc. Loptimisation combinatoire comprend un ensemble fini de solutions, o

chaque solution doit satisfaire un ensemble de contraintes relatives la nature du

problme, et une fonction objectif pour valuer chaque solution trouve. La solution

optimale est celle dont la valeur de lobjectif est la plus petite (resp. grande) dans le cas de

minimisation (resp. maximisation) parmi lensemble de solutions.

Un problme doptimisation combinatoire peut tre dfini par :

Vecteur de variables x = (x1 , ,xn)

Domaine des variables D = (D1, D2,.,Dn), o les (Di)i=1,..,n sont des ensembles

finis

8

Ensemble de contraintes

Une fonction objectif f minimiser ou maximiser

Ensemble de toutes les solutions ralisable possibles est S = {(x1, x2,xn) D / x satisfait

toutes les contraintes }, lensemble S et aussi appel un espace de recherche.

La rsolution des problmes combinatoires est assez dlicate puisque le nombre fini de

solutions ralisables crot gnralement avec la taille du problme, ainsi que sa complexit.

Cela pouss les chercheurs dvelopper de nombreuses mthodes de rsolution en

recherche oprationnelle (RO) et en intelligence artificielle (IA). Ces approches de

rsolution peuvent tre classes en deux catgories : les mthodes exactes et les mthodes

approches.

Les mthodes exactes ont permis de trouver des solutions optimales pour des problmes de

taille raisonnable et rencontrent gnralement des difficults face aux applications de taille

importante. En revanche les mthodes approches ne garantissent pas de trouver une

solution exactes, mais seulement une approximation, mais ils peuvent donner des solutions

mme pour les problmes de tailles assez grandes.

2.3.1 Prliminaire

2.3.1.1 Optimisation combinatoire

Loptimisation combinatoire ou optimisation discrte, est une branche de loptimisation

lie essentiellement aux domaines suivants :

- mathmatique appliques

- informatique

- la recherche oprationnelle

- lalgorithmique et la thorie de la complexit.

2.3.1.2 Problme doptimisation combinatoire

Un problme doptimisation combinatoire consiste trouver la meilleure solution dans

un ensemble discret dit ensemble des solutions ralisable. Cet ensemble est souvent fini

mais de cardinalit peut tre trs grande et il est dcrit de manire implicite, cest--dire

par une liste de contraintes doivent satisfaire les solutions ralisables.

9

2.3.1.3 La complexit

La complexit analyse lespace mmoire ou le temps ncessaire pour obtenir une

solution.

La thorie de complexit conduit distinguer entre la complexit des problmes et la

complexit des algorithmes utiliss pur les rsoudre.

Complexit dun problme :

On appelle complexit dun problme la complexit en temps du meilleur algorithme

permettant de le rsoudre.

Un problme peut tre rsolu par diffrents algorithmes et en gnral on nest pas sr

davoir trouv lalgorithme de meilleure complexit. Lanalyse des problmes consiste

les rangs dans des classes de problmes de complexit.

a)- La classe P

Cest lensemble des problmes pour lesquels il existe un algorithme de rsolution en

un temps polynomiale

b)-La classe NP

Cest lensemble des problmes pour lesquels il existe un algorithme non dterministe

pouvant les rsoudre en un temps polynomial.

c)-La classe NP-difficile

Un problme est NP-difficile si lexistence dun algorithme de complexit polynomiale

pour le rsoudre implique P = NP.

d)-La classe NP-complet

Un problme est NP-complet sil est NP-difficile et sil appartient la classe NP.

2.3.2 Mthodes de rsolution

La rsolution du problme doptimisation combinatoire consiste trouver une solution

optimale dans un ensemble discret et gnralement fini, ce qui est une trivialit du point de

10

vue mathmatique. Du point de vue informatique et pratique, le temps de recherche la

solution optimale est un facteur trs important et cest pour cela les problmes

doptimisation combinatoire sont rputs si difficiles. On distingue deux grandes classes de

mthodes de rsolution : les Mthodes exactes et les mthodes approches

2.3.2.1 Mthodes exactes

Le principe essentiel dune mthode exacte consiste gnralement numrer, souvent

de manire implicite, lensemble des solutions de lespace de recherche.

Les mthodes exactes ont permis de trouver des solutions optimales pour des problmes de

taille raisonnable. Malgr les progrs raliss, notamment en matire de la programmation

linaire en nombres entiers, le temps de calcul ncessaire pour trouver une solution, risque

daugmenter exponentiellement avec la taille du problme rencontrent gnralement des

difficults face aux applications de taille importante.

2.3.2.2 Mthodes approches

Les mthodes approches constituent une alternative trs intressante pour traiter les

problmes doptimisation de grande taille, leur but est de trouver une solution de bonne

qualit en un temps de calcul raisonnable sans garantir loptimalit de la solution obtenue.

Ces mthodes sont fondes principalement sur divers heuristiques, souvent spcifiques

un type de problme donn.

Lobjectif heuristique , signifie qui facilite la dcouverte, qui a une utilit dans la

recherche (scientifique ou autre) .

Les mthodes heuristiques sont des critres, des principes ou des mthodes permettant de

dterminer parmi plusieurs solutions, celle qui promit dtre la plus efficace pour atteindre

un but.

11

Chapitre 2 : Problme de gestion des examens

2.1 Introduction

Parmi les problmes dordonnancement les plus tudis dans la littrature, nous

trouvons le problme demploi du temps dans les tablissements denseignement.

Lobjectif est daffecter un ensemble dentits (cours, examens, etc) un nombre

limit de ressources (tranches horaire, salle,etc).

Ces problmes de gestion des examens sont des problmes trs tudis dans la littrature.

En effet il a fait le sujet de plusieurs travails de chercheurs dans ces derinires annes, nous

citons par exemple le travail de Ibtissam Dkhssi et Rachida Abounasser.

Le problme demploi du temps duniversit qui a eu un grand intrt le long des dernires

dcennies, est divis dans la littrature en deux problmatiques :

1) le problme demploi des temps de cours.

2) le problme demploi des temps des examens.

Ces deux types de problme se ressemblent, mais il y a certaine nombre de points de

diffrences entre eux.

Dans ce chapitre nous tudions le problme demploi du temps des examens connu aussi

sous le nom de gestion des examens.

2.2 Problme demploi du temps des examens

Le problme demploi du temps des examens est concern par lattribution dun

ensemble E = {e1,..,en} des examens dans un ensemble T = {T1,..,TM} de crneaux

horaires sous un certain nombre de contraintes fortes et faibles. Les contraintes fortes

doivent tre satisfaites afin de produire un planning ralisable, tandis que les contraintes

faibles doivent tre rduites au minimum.

Les contraintes fortes du problme demploi du temps les plus frquents dans la

littrature sont :

1) aucun tudiant ne doit avoir plus de deux examens dans la mme tranche horaire.

12

2) la capacit de ltablissement ne doit pas tre dpasse nimporte quelle tranche

horaire donne.

3) certaines paires dexamens peuvent subir des contraintes de priorit ou de

simultanit. Un ensemble de contraintes fortes moins communes peuvent souvent tre

considres dans diffrents tablissements selon leurs exigences particulires.

Les contraintes faibles varient bien plus que les contraintes fortes parce quelles dfinissent

essentiellement la qualit de lemploi du temps afin de donner une mesure de comparaison

parmi les emplois du temps ralisable. Afin dutiliser une fonction objectif simple

optimiser, ces contraintes faibles doivent toutes tre pondres selon leurs importance

relative pour le planning produit. Citons quelques exemples des contraintes faibles les plus

confrontes dans la littrature :

1) Affectation des crneaux horaire : il peut tre dsir quun examen soit planifi dans

une tranche horaire particulire.

2) Contraintes de prcdence entre les vnements : un examen doit tre planifi avant ou

aprs dautres (selon le problme, cette contrainte peut tre galement une contrainte

forte).

3) Distribution des vnements le long de lhorizon de planification : les tudiants ne

doivent pas avoir des examens en priodes conscutives et de prfrence spares au

maximum.

4) affectation des ressources : il peut tre dsir quun examen soit affect dans une salle

particulire.

Certain tablissement considrent galement la contrainte concernant le placement de

plusieurs examens dans une mme salle u la contrainte qui permet que les tudiants inscrits

dans un mme examen peuvent tre placs dans plusieurs salles. Le nombre de tranches

horaire dans lhorizon de planification peut tre fix priori ou il peut intervenir comme

objectif minimiser. Cette contrainte reprsente un conflit avec la contrainte qui consiste

taler les examens le long de lhorizon de planification. Dautres contraintes faibles

peuvent apparaitre selon la spcifit de ltablissement par exemple une facult des

sciences na pas les mme contrainte que une FST ou quune cole dingnieure

13

2.3 Problme apparus dans la littrature

Laccroissement de lintrt de recherches pour les problmes demploi du temps des

examens a men les chercheurs (Carter et al. [CARTER 96]) la cration dun ensemble

de problmes qui ont t largement tudis dans la littrature. Les problmes tablis, sont

dfinis suivant certaines mesures dfinissant les variantes, qui fournissent une manire

pour tablir des comparaisons scientifiques. Cependant, il y a eu une manire pour tablir

des comparaisons scientifiques. Cependant, il y a eu une certaine confusion dans la

littrature due lapparition de deux versions diffrentes de huit instances de ces

problmes (de luniversit de Toronto). Nous essayons de prsenter les diffrents

problmes apparus dans la littrature :

Problmes de luniversit de Toronto

Carter et al. [CARTER 96] ont prsent un ensemble dinstances du problme

demploi du temps des examens rels de trois lyce canadiens, de cinq universits

canadiennes, dune universit amricaine, dune universit britannique et dune universit

en Arabie Saoudite. Ces problmes ont t largement tests dans la littrature par

diffrentes approches et sont considres comme des rfrences.

Deux variantes des objectifs ont t dfinies :

1- la minimisation du nombre de tranches horaires requis pour le problme (appele

Torontoa)

2- la minimisation du cot moyen par tudient (appel Torontob)

pour le premier objectif, le but est de construire un planning faisable dans un horizon de

longueur minimale. Pour le deuxime objectif, une fonction dvaluation a t dfinie pour

calculer le cot des plannings produits. Pour un tudiant ayant deux examens spars par s

tranches horaires, le cot associ est dfini par la valeur de proximit ws o w1 = 16, w2 =

8, w 3 = 4 w4 = 2 et w5 =1. Le but est de sparer deux examens conscutifs au maximum

dans lhorizon de planification fix.

14

Les auteurs ont galement prsent sept autres instances du monde rel avec dautres

contraintes latrales (par exemple : la capacit maximal des salles par tranche horaire, le

nombre maximal dexamen par tranche horaire,.etc)

Burke et al. [BURKE 96] nt modifi lobjectif des variantes du monde rel prsentes dans

[CARTER 96] en considrent la contrainte de la capacit maximal des salles par tranches

horaires dans les problmes nt t distingues en plaant trois horaires par jour de lundi au

vendredi et une tranche horaire samedi. Lobjectif est de minimiser le nombre des tudiants

passant deux examens conscutif dans le mme jour et durant la nuit. Ces deux variantes

sont appeles Torontoc et Tonrontod. Terashima-Marin et al. [TERASHIMA-MARIN 99]

ont modifi lensemble de donnes en affectant chaque instance du problme un nombre

de tranches horaires estim et chaque tranche horaire la capacit maximal des salles.

Cette variante est appele Torontoe

Variantes bjectifs

Toronto a Minimisation du nombre des tranches horaires ncessaires

Toronto b Maximiser de la sparation entre les examens dans un horizon de

planification fix

Toronto c Minimiser des nombres des tudiants ayant deux examen dans le mme

Toronto d Pariel que dans Toronto c : minimisation des tudiants passant deux

examens durant la nuit

Toronto e Minimisation du nombre des tudiants passant deux examens dans deux

tranches horaires adjacents

Problme de luniversit de Nottingham

En plus des objectifs tudis dans les problmes de Tonronto, Burke et al. [BURKE 98

a] ont introduit lobjectif de minimisation du nombre des examens conscutifs durant la

nuit. Ces nouvelles variantes des problmes demploi du temps des examens ont t

appels Nottingham a et Nottingham b .

Problme de luniversit de Melbourne

Merlot et al. [MERLOT 03] ont prsent un ensemble de donnes du problme demploi

du temps des examens de luniversit de Melbourne. Sont objectif est de minimiser le

nombre dexamens adjacents dans le mme jour

15

2.3 Problmatique

Les responsables des services des examens confrontent des problmes au niveau

dorganisation les horaires des examens.

Comment organiser les examens dont le minimum de chrnos possible et sous la condition

quaucun tudiant nait passer deux preuves en mme temps ?

2.4 Reprsentation des solutions

2.4.1 Reprsentation graphique

La forme la plus simple d'un problme de gestion des examens est quivalente celle de la

coloration des graphes, Ce problme consiste colorier les sommets d'un graphe G de

faon ce que deux sommets relis par un arc ne soient jamais de la mme couleur.

Lobjectif de ce problme est la minimisation du nombre de couleurs. Par analogie, en

posant les examens comme des sommets et les couleurs comme des priodes, chaque

examen doit tre assign une seule priode. De plus, les examens qui ont des lves en

commun, qui sont relis par un arc, ne doivent pas tre assigns une mme priode.

2.4.2 Reprsentation matricielle

Dans le problme demploi du temps des examens, nous peuvent transformer le problme

sous forme dune matrice carr symtrique C o chaque lment Cij = 1 si lexamen i est

en conflit avec lexamen j cest--dire que i et j ont des tudiants en commun, et Cij = 0

sinon.

Exemple

2.5 Conclusion

La recherche dans le problme demploi du temps a commenc par des techniques

squentielles simples pendant les annes 60. Les techniques bases sur les contraintes sont

apparues plus tard et jouent toujours un rle significatif nos jours. les recherches

rcentes dans le problme demploi du temps des examens sont domines par les

mtaheuristiques et leurs hybridations avec un ensemble de techniques, incluant plusieurs

techniques rcentes, les techniques de recherche locale est des techniques multicritres qui

ont galement prsent des rsultats intressants.

16

Dans le quatrime chapitre de ce mmoire nous tudions lorganisation des examens dans

un semestre la FST de Fs, et nous essayons de rsoudre ce problme on utilisant les

proprits de la coloration des graphes.

17

Chapitre 3 : Coloration des graphes

3.1 Introduction

En recherche oprationnelle, le problme de la coloration de graphe fait partie

des problmes de rfrence. Il consiste minimiser le nombre de colorier les sommets dun

graphe donn de telle sorte que deux sommets lis par une arte naient pas la mme

couleur.

La coloration de graphes remonte 1852, lorsque Francis Lutherie a prsent sa conjecture

des quatre couleurs, chaque carte peut tre colore avec quatre couleurs de sorte que les

pays voisins qui partagent une frontire commune reoivent des couleurs diffrentes .

Depuis, la coloration de graphes est devenu lun des domaines les plus tudis de la thorie

de graphes.

Pour colorier un graphe tel quil nexiste pas deux sommets adjacents ayant la mme

couleur est le principe problme dtude en coloration de graphe. Le problme de la

coloration de graphe est parmi les problmes doptimisation combinatoires les plus tudis

en informatique et en mathmatique. La coloration de graphes et un sujet trs actif de la

thorie des graphes, il fait objet de plusieurs applications et de problmes rel dans de

nombreux domaines tels que, la tlcommunication, la bioinformatique et linternet. Est li

de nombreuses applications traditionnelles dans des domaines varis, comme le problme

demploi du temps, lordonnancement des tache, etc.la coloration de graphes a t aussi

applique pour modliser et rsoudre des problmes en mathmatiques et statistique.

Dans ce chapitre nous essayons de donner quelque proprit sur le problme de coloration.

Ensuite nous introduisons les mthodes de relaxation, avec en particulier la relaxation

surrogate, et Nous proposons une heuristique pour la rsolution du problme de

lensemble indpendant maximal (MIS) base sur la relaxation surrogate de la formulation

en programmation entire du problme (MIS).

18

3.2 Coloration dun graphe

3.2.1 Ensemble indpendant

Un ensemble indpendant ou stable dun graphe G = (V, E) est un sous-ensemble S

incluse dans V de sommets deux deux non relis par une arte. On note par (G)

(nombre de stabilit) le cardinal maximum dun stable de G. Notons quun stable est le

complmentaire dune clique et que

(G) = (G) ainsi que (G) = (G), ou (G) est la taille de la clique maximale de G.

3.2.2 Coloration de graphe

Soit k un entier. On appelle k-coloration du graphe G = (S, A) toute partition de S en

k ensembles A1 ,Ak tels que pour tout 1 i k, G[Ai] est un stable. Les ensembles

Ai sont appels les couleurs de G. si x Ai, on dit quon a donn x la couleur i. notons

quun graphe n sommets possde une n-coloration.

On appelle nombre chromatique de G le plus petit entier k tel que G admet une k-

coloration. On note (G) le nombre chromatique de G.une coloration de G avec (G)

couleurs est dite optimal. On note (G) (resp., (G)) la taille dune clique (resp. dun

stable) de G de taille maximal ; autrement dit (G) := max {| C | : C est une clique de G }

(resp., (G) = max{| C| : C est un stable de G}), o C dsigne le nombre dlments de

|C|.

(G). (G) n(G)

n(G) tant le nombre de sommets du graphe.

On a aussi :

(G) deg G + 1

O deg G est le plus grand degr dun sommet.

Do :

deg G + 1 (G)

19

Dfinition :

Lindice chromatique not q(G) dun graphe G est le nombre minimal de couleurs

ncessaires la coloration des artes de G.

Exemple

A B

C D

2.3 Problme densemble indpendant maximal

2.3.1 Relaxation

Un problme doptimisation P : max {f(x), x S1} est une relaxation du problme

PR : max {f(x), x S2} si S2 incluse dans S1, une relaxation dun problme est une

formulation qui contient un ensemble de solutions ralisables plus grand que celui du

problme original, et donne une borne suprieure du problme PR. Dans le cas dun

problme de minimisation, la relaxation fournit une borne inferieure. Une bonne relaxation

fournit une solution optimale proche de loptimum du problme original.

De manire gnrale, une relaxation devrait satisfaire les deux conditions suivantes :

Avoir une structure semblable celle du problme original

Plus facile rsoudre que le problme original, de manire fournir de bonnes bornes.

2.3.2 Relaxation Surrogate

La relaxation surrogte ou bien agrge a t initialement prsente comme un moyen

damliorer les rgles de dcision et borner linformation dans des algorithmes de la

programmation entire (Glover 1965). La relaxation surrogate consiste combiner

lensemble des contraintes en une seule de manire suivante :

max c t.x

( IP) A.x b

x {0, 1}n

20

O x = (x1,, xn) t, c = (c1,.,cn), b = (b1,..,bm)

t , A = aij pour 1 i m et

1 j n.

La relaxation surrogate est donne par :

max ct .x

(SC) w t A. x w t b

x {0,1}

Avec 0 w = (w1,.wn) t

2.3.4 Problme densemble indpendant maximal

Le problme densemble indpendant maximal est lun des problmes centraux de

loptimisation, et un des problmes classiques montrs pour tre NP-difficile, son intrt

augmente en raison de son quivalence au problme de la clique maximale et celui de

couverture. Il est efficace pour la rsolution de nombreuses applications pratiques en

informatique, en recherche oprationnelle, ou dans le domaine de lingnierie, telles que le

problme dordonnancement, le problme de coloration de graphes, etc.

2.3.5 Formulation du problme densemble indpendant maximal

Nous considrons un graphe non-orient G = (V, E), o V = {1,..n} dnote

lensemble de sommets du graphe G et E dnote lensemble des artes. i V on a

nodestar(i) = {j : {i,j} E}

di = card(nodestar(i))

d0 = |E| = nombre des artes.

La formulation usuelle de la programmation mathmatique pour le problme densemble

indpendant maximal associe une variable binaire xi chaque sommet i V telle que

1 si le sommet est choisi comme lment de lensemble indpendant maximal

xi =

0 sinon

21

2.3.6 Modlisation Mathmatique

Lobjectif

Maximiser le nombre de sommets dun stable

Variable

xi sommet dun graphe G

Contrainte

Lensemble indpendant ne contient que les sommets non adjacents c.--d. quil que soit

un arc dont les extrmits sont i, j alors forcement au plus lun de ce sommets sera dans

notre ensemble indpendant maximal.

Do la formule mathmatique est donn par :

xi + xj 1 (i, j) E

Donc le problme peut tre exprim sous forme dun problme de la programmation en

nombres entiers comme suit :

max x0 = (xi : i V)

(IP) xi + xj 1, {i, j} E

xi binaire, i V

Les variables de dcision correspondent aux opration faites sur un graphe tels

quajouter ou supprimer des sommets et des artes. De mme, des implications de la

dcision telles que forces des variables particulires prendre la valeur 0 ou 1 et faire

exprimer des contraintes redondants peuvent galement tre refltes par des changements

correspondants la structure de graphe. Dans le cas actuel, selon le problme considr, le

problme (IP) correspondent aux rductions simples suivantes du graphe :

Poser xi =1 dans le problme (IP), force xj = 0 pour toutes les variables xj telles que

xi +xj 1 ce qui correspond dans le graphe

22

2.3.7 Amlioration de la solution de la contrainte surrogate

Le problme de lensemble indpendant maximal est exprim comme suit :

max x0 = (xi : i V)

(IP) xi + xj 1, {i, j} E

xi binaire, i V

pour produire rapidement une solution approche de ce type de problme, nous

utilisons lheuristique de la contrainte surrogate, obtenue on remplaant lensemble des

contraintes par une seule contrainte combinaison linaire des originales. Les poids di sont

obtenus en additionnant le nombre de fois o xi apparait dans les ingalits, et d0 est le

nombre de toutes les ingalits pour le problme (IP).

Pour le problme (IP), nous faisons une simple sommation de toutes les contraintes comme

suit :

(di xi: i V) d0

Le problme surrogate associ (IP) est :

max x0 = (xi : i V)

(SC) (di xi : i V) d0

xi binaire, i V

la valeur de d0 dans les contraintes du problme surrogate (SC) est gale au nombre de

contraintes dingalit, et di est gale la somme des coefficients dunit pour les variables

xi qui apparaissent dans ces contraintes pour avoir une meilleure solution nous pouvons

inclure certaines contraintes de (IP) dans le problme (SC) de la manire suivante :

max x0 = (xi : i V)

(di xi : i V) d0

(SC1) xi + xj 1, {i, j} E

xi binaire, i V

23

O E contient des artes de E formes par des paires de sommets disjoints, et par

consquent chaque variable xi, i V, apparat au plus une fois dans la collection des

ingalits.

Sous la condition de croissance des di nous dfinissons :

V = V- {j V: (i, j) E et i< j}

Par consquent lensemble V est obtenu en abandonnant dans chaque arte (i, j) E les

sommets du plus grand coefficient. Alors les contraintes auxiliaires dans E peuvent tre

enleves et le problme est rduit :

max x0 = (xi : i V)

(SC2) (di xi : i V) d0

xi binaire, i V(SC2)

Nous remarquons que (SC2) a la mme forme que le problme de la contrainte

surrogate original (SC), et puisque V enlve presque la moiti des coefficients de V, donc

la solution est plus restreinte et SC2 donne gnralement une borne x0 de meilleure qualit

que (SC).

Exemple 2.1

Nous considrons un graphe non-orient dans la figure 2.1, nous essayons dappliquer

lapproche de la contrainte surrogate utilisant les deux transformations (SC1) et (SC2) afin

davoir un ensemble indpendant maximal V. Le en nombre entiers associ ce graphe

peut sexprimer sous la forme :

24

max x0 = i V xi

x1 + x2 1

x1 + x3 1

x2 + x3 1

x2 + x5 1

(IP) x2 + x6 1

x3 + x5 1

x3 + x6 1

x4 + x5 1

x4 + x6 1

x5 + x6 1

xi binaire, i V

Figure 1 Extraction de lensemble indpendant maximal

Nous introduisons par la suite lapproche surrogate donne dans (2.1), ainsi le programme

surrogate (SC) associ (IP) est de la forme :

max x0 = iV xi

(SC) 2x1 + 4x2 + 4x3 + 2x4 + 4x5 + 4x6 10

xi binaire, i V

1

0

0

0

0

2

3 5

6

4

25

Lensemble dartes E E constitu de paires de sommets disjoints (les contraintes

redondantes) correspond au graphe de la figure 2.1 est E = {(1, 2), (3,5), (4 ,6)} et donc le

problme (SC2) associ scrit sous la forme :

max x0 = iV xi

2x1 + 4x2 + 4x3 + 2x4 + 4x5 + 4x6 10

(SC1) x1 + x2 1

x3 + x5 1

x4 + x6 1

xi binaire, i V

Puisque les sommets du graphe sont ordonns dune manire croissante suivant leurs

degrs, nous liminons tout sommet j els que (i, j) et i < j, lensemble de

sommets enlev est {2, 6, 5}, par consquent V= {1, 3, 4} est lensemble de sommets qui

sont rests.

Aprs avoir limin toutes les contraintes redondantes du problme (SC), nous obtenons

donc le problme suivant : max x0 = iV xi

(SC2) x1 + x3 1

xi binaire, i V

Figure 2 graphe rsultant aprs rduction de variables.

Nous pouvons illustr cette rduction de variables sous forme dun graphe de la figure

2.2.

Le problme (SC2) la mme structure que le problme surrogate (SC), on refait alors les

mmes tapes prcdentes on a lensemble V = {1,4}

1

3

4

26

2.3.8 Amlioration par une mthode base sur le multiplicateur w de la contrainte

surrogate

Pour le cas dun graphe G = (V, E) non orient, nous considrons w = (w1,..,wm)t,

avec m le nombre dartes. On nonce dabord le rsultat suivant :

Rsultat

Soit (SC) la relaxation surrogate du problme (IP), on choisit la variable xr =1, si ak,j =1

avec j = nodestar (r) alors wk =0, pour tout 1 j n et 1 k m (Douiri et El Bernoussi)

Preuve

Pour xr et j nodestar(r) nous posons k=1 ak,j = dj ( nombre darrtes relies au sommet j)

nous avons :

Wt.A.x = wl.al,1.x1 + .+ = wl.al,n.xn ()

Le choix xr = 1 implique xj = 0, donc toutes les artes associes j seront limines,

autrement dit si ak,j =1 on lui donne la valeur zro k 1, . , ,et en utilisant la relation

() cela sexprime par wk =0.

Nous utilisant un algorithme de construction dun ensemble indpendant maximal

approch. Lalgorithme est donne par :

1. Poser w = (1,..,1)t et V = .

2. Calculer la contrainte surrogate wt A = wk 0 (ak).

3. Donner i = indice (min (wtA) : (w

tA)i 0), poser xi = 1 et V = V

4. pour tout j nodestar (i), si ak,j = 1 alors wk = 0,si k=1 wk = 0 stop.

Autrement retourner ltape 2.

27

Sur le graphe de lexemple 2.1, nous appliquons cette lalgorithme pour donner un

ensemble indpendant maximal, nous considrons la matrice de graphe A = (ai,j) suivante :

1 1 0 0 0 01 0 1 0 0 00 1 1 0 0 00 1 0 0 1 00 1 0 0 0 10 0 1 0 1 00 0 1 0 0 10 0 0 1 1 00 0 0 1 0 10 0 0 0 1 1

Pour w = (1,1,1,1,1,1,1,1,1,1)t nous avons SC = w

t A = (2,4,4,2,4,4).

indice (min(wt A) : (w

t A)i 0) = 1 alors V = {1}.

nodestar (1) = {2,3} nous cherchons 1 k 12 tel que ak,2 = 1 et ak,3 = 1 donc

k ={1,2,3,4,5,6} et w = (0, 0, 0, 0, 0, 0, 0,0, 1, 1, 1)t.

Nous recalculons SC = (0, 0, 0, 2, 2, 2) et indice (min (wt A): (w

t A)i 0) = 4 donc

V= {1, 4}.

nodestar (4) = {5,6}, nous identifions les valeurs de k de sorte que ak,5 = 1 et ak,6 = 1 ce qui

donne k = { 4, 5, 6, 7, 8, 9, 10} alors w = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}t

V nodestar 1, 4 Valors V = V { V/ nodestar (1, 4) V } = {1, 4} correspond

lensemble indpendant maximal.

28

Chapitre 4 : Application a Un semestre la FST de Fs

4.1 Introduction

La coloration de graphe est la base de modlisation de plusieurs problmes rels,

comme le problme de gestion des examens, qui consiste colorier les sommets dun

graphe G de faon ce que deux sommets relis par un arc ne soient jamais de la mme

couleur, lobjectif de ce problme est la minimisation du nombre de couleurs. Dans le

contexte des horaires, les sommets de G reprsentent les examens alors que les couleurs

reprsentent les priodes consacres la tenue des examens. Chaque examen doit tre

assign une seule priode. De plus, les examens qui ont des lves en commun, qui sont

relis par un arc, ne doivent pas tre assigns une mme priode.

4.2 Rsolution du problme de gestion dexamen

4.2.1 Application un semestre la FST de Fs

La Facult des sciences et Techniques-Fs doit organiser les horaires des examens dun

semestre qui contient (S1, S2, S3, S4, S6) Cinquante-deux preuves planifier,

correspondant aux cours numrots de 1 52

Comment organiser ces examens dont le minimum de chrnos possible et sous la

contrainte quaucun tudiant nait passer deux preuves en mme temps ?

On numrote les modles de 1 jusqu' 52

S1 contient les 4 modles M1, M2, M3, M4

Soit E1 lensemble des tudiants qui sont inscrit au modle M1 (1)

E2 lensemble des tudiants qui sont inscrit au modle M2 (2)




soit E5 lensemble des tudiants qui sont inscrit au modle M5 (5)

29









CAM-S4 contient les 4 modles M13, M14, M15, M16





CAM-S6 contient les 4 modles M21, M22, M23, M24





CSA-S4 contient les 4 modles M13, M14, M15, M16





30

CSA-S6 contient les 4 modles M21, M22, M23, M24





ETI-S4 contient les 4 modles M13, M14, M15, M16





ETI-S6 contient les 4 modles M21, M22, M23, M24





GIND-S4 contient les 4 modles M13, M14, M15, M16





GIND-S6 contient les 4 modles M21, M22, M23, M24



31



GINF-S4 contient les 4 modles M13, M14, M15, M16





GINF-S4 contient les 4 modles M21, M22, M23, M24





E1

ALLOUCH REDA, BOUNNOUH AMINE, DZIRI HAMZA, ER-RAGRAGUI SALAH EDDINE, MOUHIB OTHMAN, SEBTI MOHAMMED, ABBOU RACHID, AFOURAOU AMAL, AKEL SOUMAYA, BELKHOU JIHANE, BENSLIMANE ASMAE, BERRAHO FADOUA, BOUADLIATTAR AYMEN, BOUCHRI YOUSRA, BOUKHRISS HAMZA, BOUYARMANE MOHAMMED, BOUZAFFOUR MOHAMED, BOUZAID MOHAMED, CHABLI BILAL, CHOUIREF ZINEB, CHOUKRY YOUSSEF, CHRIFI ALAOUI A BBES, EL BARAKA AMAL, EL GANDOULI YOUSSEF, EL KHOMSI SABRINE, ELASSRI AMINE, EL-MRABET AMINA, ERROUDI WAFAE, HOUSNI NAIM, JABER ASMAE, KADDOURI YASSINE, KAINI SAAD, LAAYOUN NAWAL, LEFAF ADIL, MADINI OUALID, MEJAHED KAUTAR , MOUFID RABAB, MOUNAIME RIHAB, MOUNOUAR OTHMANE, MOUSTAHSINE SMAIL, NADAH IBRAHIM, NAH FOUAD, NALI MOHSSINE, OUKICHA NAJWA, RABHI SORAYA, RHALEB BASMA, SEDIKI YASSINE, TAIBI ZINEB, TAMIMI SOUFIANE, TLEMCANI YOUSSEF, NACHIT ZOUHIR)

E2

BOUZIDI MOHAMMED ABDERRAHMANE, MOUHIB OTHMAN, CHRIFI ALAOUI A BBES, EL BARAKA AMAL, ELASSRI AMINE, EL-MRABET AMINA, JABER ASMAE, LEFAF ADIL, MADINI OUALID, MOUSTAHSINE SMAIL, TAIBI ZINEB, ZOUINE MOHAMMED AMINE

E3 LOUDYI KHADIJA, AKEL SOUMAYA, CHOUKRY YOUSSEF, EL BARAKA AMAL, IDIR CHAFIQ, MOUSTAHSINE SMAIL, TAIBI ZINEB, ZOUINE MOHAMMED AMINE

E4 CHOUKRY YOUSSEF, NAH FOUAD

E5

LOUDYI KHADIJA, BOUADLI ATTAR AYMEN, CHABLI BILAL, CHOUIREF ZINEB, EL HABCHI BADR, ELASSRI AMINE, ELKACHCHABI YASSIR, IDIR CHAFIQ, RABAH NABIL, SADIK SOUKAINA

BENMOUSSA MAROUA, DKAKI OUMAYMA, ELHILALI NOURA, LOUDYI KHADIJA,

32

E6

MOUHIB OTHMAN, TIJAHI FATIMA ZAHRAE, BELFAKIH ILHAM, BELMAJDOUB ISMAIL, BENSLIMANE ASMAE, BERRAHO FADOUA, BOUADLI ATTAR AYMEN, BOUCHRI YOUSRA, BOUKHRISS HAMZA, BOURI YOUSRA, CHAIBI FATIMA ZAHRAE, CHOUIREF ZINEB, EL HABCHI BADR, ELASSRI AMINE, ELKACHCHABI YASSIR, IDIR CHAFIQ, JABER ASMAE, MADINI OUALID, MEJAHED KAOUTAR, MOUFID RABAB, MOUNAIME RIHAB, NAH FOUAD, NALI MOHSSINE, OULD AHMED OULD HAMIDOUN MOKHTAR, RABAH NABIL, RABHI SORAYA, RHALEB BASMA, SAADAOUI ISSAM, SADIK SOUKAINA, SEKKAT ABDERRAHIM, STITOU BOUZID, TAIBI ZINEB, TAOUIL MERYEM, TLEMCANI YOUSSEF, TOULOUT SALMA, ZOUINE MOHAMMED AMINE, LAKRAMTI FIRDAOUS, MATTOUHI MERIEM, TELMANI NASSIRA

E7

BELFAKIH ILHAM, BELKHOU JIHANE, BENSLIMANE ASMAE, BOUADLI ATTAR AYMEN, BOUKHRISS HAMZA, BOURI YOUSRA, CHABLI BILAL, CHOUIREF ZINEB, EL GANDOULI YOUSSEF, EL HABCHI BADR, LAAYOUN NAWAL, LEFAF ADIL, MEJAHED KAOUTAR, SAADAOUI ISSAM, SADIK SOUKAINA, SEDIKI YASSINE, TAOUIL MERYEM, TLEMCANI YOUSSEF, ZOUINE MOHAMMED AMINE, TELMANI NASSIRA

E8 SAADAOUI ISSAM

E9

BALLOUK KARIMA, BENISS MOHAMED AMINE, BOUNNOUH AMINE, DJAZI MEHDI, DKAKI OUMAYMA, ECHCHERKI OUSSAMA, EDDARIF FATIHA, ER-RAGRAGUI SALAH EDDINE, ESSAHAL WALID, EZZENATI SARA, HEDDA SARA, LADRAA AICHA, LOULIDI YASSINE, SEBTI MOHAMMED, TIJAHI FATIMA ZAHRAE, ABBOU RACHID, AFOURAOU AMAL, AKEL SOUMAYA, BELKHOU JIHANE, BELMAJDOUB ISMAIL, BERRAHO FADOUA, BOURI YOUSRA, BOUYARMANE MOHAMMED, BOUZAFFOUR MOHAMED, BOUZAID MOHAMED, CHABLI BILAL, CHAIBI FATIMA ZAHRAE, CHOUKRY YOUSSEF, CHRIFI ALAOUI A BBES, DOBLI BENNANI ABDESSALAM, EL BARAKA AMAL, EL GANDOULI YOUSSEF, EL KHOMSI SABRINE, ELKACHCHABI YASSIR, EL-MRABET AMINA, ERROUDI WAFAE, HOUSNI NAIM, IDIR CHAFIQ, KADDOURI YASSINE, KAINI SAAD, LAAYOUN NAWAL, MOUNOUAR OTHMANE, NADAH IBRAHIM, NAH FOUAD, NALI MOHSSINE, OUARD ZINEB, OUKICHA NAJWA, OULD AHMED OULD HAMIDOUN MOKHTAR, RHALEB BASMA, SEDIKI YASSINE, SEKKAT ABDERRAHIM, TAMIMI SOUFIANE, TAOUIL MERYEM, TOULOUT SALMA, FILALI MOUHIM ISSAM, M'HAMDI HAJAR, MOUFID FATIMA ZAHRA, BENBOUBKER HAMZA, BENJELLOUN MOHAMMED SALIM, EL YAMANI MERYEM, MOUSLIH GHIZLANE, IDRISSI MELIANI MOHAMMED, SENHAJI MEHDI, TAHRI JOUTEI ZINEB, ZEHOUANI FATMA, ALIOU DIALLO AOUDI MOHAMED HABIB, CHAOUQUI AKRAM

E10

ALLOUCH REDA, BENISS MOHAMED AMINE, BOUNNOUH AMINE, BOUZIDI MOHAMMED ABDERRAHMANE, DJAZI MEHDI, DZIRI HAMZA, ECHCHERKI OUSSAMA, EDDARIF FATIHA, ESSAHAL WALID, EZZENATI SARA, HEDDA SARA, LADRAA AICHA, ABBOU RACHID, AFOURAOU AMAL, AKEL SOUMAYA, BELMAJDOUB ISMAIL, BOUCHRI YOUSRA, BOUZAFFOUR MOHAMED, BOUZAID MOHAMED, CHAIBI FATIMA ZAHRAE, DOBLI BENNANI ABDESSALAM, EL KHOMSI SABRINE, ELKACHCHABI YASSIR, ERROUDI WAFAE, HOUSNI NAIM, KADDOURI YASSINE, KAINI SAAD, MOUNAIME RIHAB, NALI MOHSSINE, OUARD ZINEB, RAFIE SOUMIA, SEKKAT ABDERRAHIM, TOULOUT SALMA, M'HAMDI HAJAR, MOUFID FATIMA ZAHRA, EL YAMANI MERYEM, TCHICH GHITA

E11

ALLOUCH REDA, BALLOUK KARIMA, BENMOUSSA MAROUA, BOUZIDI MOHAMMED ABDERRAHMANE, DJAZI MEHDI, DKAKI OUMAYMA, ECHCHERKI OUSSAMA, EDDARIF FATIHA, ELHILALI NOURA, ESSAHAL WALID, EZZENATI SARA, HEDDA SARA, LADRAA AICHA, LOULIDI YASSINE, TIJAHI FATIMA ZAHRAE, ABBOU RACHID, BELMAJDOUB ISMAIL, BERRAHO FADOUA, BOUCHRI YOUSRA, CHAIBI FATIMA ZAHRAE, CHRIFI ALAOUI A BBES, EL GANDOULI YOUSSEF, HOUSNI NAIM, KADA OUMAIMA, KADDOURI YASSINE, KAINI SAAD, LAAYOUN NAWAL, MOUNAIME RIHAB, NADAH IBRAHIM, OUARD ZINEB, OUKICHA NAJWA, OULD AHMED OULD HAMIDOUN MOKHTAR, RAFIE SOUMIA, STITOU

33

BOUZID, TAMIMI SOUFIANE, TOULOUT SALMA, DAROUICHE BAHIJA, MOUFID FATIMA ZAHRA, TCHICH GHITA, ALIOU DIALLO AOUDI MOHAMED HABIB, CHAOUQUI AKRAM

E12

ALLOUCH REDA, BALLOUK KARIMA, BENISS MOHAMED AMINE, BENMOUSSA MAROUA, BOUNNOUH AMINE, BOUZIDI MOHAMMED ABDERRAHMANE, DJAZI MEHDI, DKAKI OUMAYMA, DZIRI HAMZA, ECHCHERKI OUSSAMA, EDDARIF FATIHA, ELHILALI NOURA, ER-RAGRAGUI SALAH EDDINE, ESSAHAL WALID, EZZENATI SARA, HEDDA SARA, LADRAA AICHA, LOUDYI KHADIJA, LOULIDI YASSINE, MOUHIB OTHMAN, SEBTI MOHAMMED, TIJAHI FATIMA ZAHRAE, SBAI AMIN, ELMEKAOU OUSSAMA, BOUYARMANE HOUDA, MOUFID FATIMA ZAHRA

E13 HADDAOUI SABAH, LAHLOU DRISS


E15


E17 BOUYARMANE HOUDA, EL GHAYATY MOHAMMED, NACHIT ZOUHIR

E18 NACHIT ZOUHIR

E19 EL GHAYATY MOHAMMED

E20 EL GHAYATY MOHAMMED

E21 ASSEMLAL ISSAM, BAKHRI ASSINE, BOUMAIS MOHAMMED, SKIREDJ MOHAMED, ZGHIMRI ACHRAF, GHAZOUANI FATIMA ZAHRA

E22 SBAI AMIN, ASSEMLAL ISSAM, BAKHRI YASSINE, BERTAL HANANE, BOUMAIS MOHAMMED, IDRISSI HANANE, SKIREDJ MOHAMED, ZGHIMRI ACHRAF, ELANSARI MOHAMMED, MEJBAR MOHAMMED REDA

E23 ASSEMLAL ISSAM, BAKHRI YASSINE, BOUMAIS MOHAMMED, IDRISSI HANANE, SKIREDJ MOHAMED, MEJBAR MOHAMMED REDA

E24 BOUMAIS MOHAMMED, SKIREDJ MOHAMED, EL HAMMOUMI MOHAMMED

E25 EL HANAOUI RABIE, EN-NASYRY ALAE, ALIOU DIALLO AOUDI MOHAMED HABIB, SKIREDJ MOHAMED, MEJBAR MOHAMMED REDA, TELMANI NASSIRA, CHAOUQUI AKRAM, EL HAMMOUMI MOHAMMED

E26 EL HANAOUI RABIE, EN-NASYRY ALAE, ALIOU DIALLO AOUDI MOHAMED HABIB, SKIREDJ MOHAMED, MEJBAR MOHAMMED REDA, TELMANI NASSIRA, CHAOUQUI AKRAM, EL HAMMOUMI MOHAMMED

E27 EL HANAOUI RABIE, EN-NASYRY ALAE

E28 EL HANAOUI RABIE, EN-NASYRY ALAE

E29 ELMEKAOUI OUSSAMA

E30 ELMEKAOUI OUSSAMA, CHRAIBI MERYEME, REZKI KHADIJA

E31 REZKI KHADIJA, SALIM MOHAMMED

E32 ELMEKAOUI OUSSAMA

E33 DABIRE NAMBOUNON ERIC, IDRISSI MELIANI MOHAMMED

E34 ERROUHA MUSTAPHA

E35 EL BELGHITI ALAOUI MOHAMMED NABIL, ERROUHA MUSTAPHA

E36 EL BELGHITI ALAOUI MOHAMMED NABIL, ERROUHA MUSTAPHA

E37 AHOUFI ANAS, LEGRA SOW MAHMOUD

E38

E39 OUENJLI SOUMAYA, AHOUFI ANAS, LEGRA SOW MAHMOUD

E40 OUENJLI SOUMAYA

E41 ERROUHA MUSTAPHA

E42 SENHAJI MEHDI, TAHRI JOUTEI ZINEB

E43 LEGRA SOW MAHMOUD

E44 LEGRA SOW MAHMOUD

E45 BOURAKKADI MOHAMMED, DAROUICHE BAHIJA, EL ARAB YAHIA, HAMEDOUN

34

MOHAMMED JABER

E46 EL ARAB YAHIA, EL ISSAOUI NAOUFAL, FILALI MOUHIM ISSAM, LAHRICHI SAFAE

E47 BOURAKKADI MOHAMMED, DAROUICHE BAHIJA, EL ARAB YAHIA, HAMEDOUN MOHAMMED JABER

E48 BOURAKKADI MOHAMMED, EL ARAB YAHIA, FILALI MOUHIM ISSAM, HAMEDOUN MOHAMMED JABER, LAHRICHI SAFAE

E49 TIJANI NASSER

E50 TIJANI NASSER

E51 TIJANI NASSER

E52 TIJANI NASSER

4.2.2 Rsolution du problme de gestion des examens

Nous utilisant la coloration des graphes pour rsoudre ce problme, nous essayons tout

dabord de transformer le problme sous forme dune matrice carr symtrique contient 0

et 1, 1 si i et j sont deux modules de mme spcialit o sils ont au moins un tudiant

rserve en commun et 0 sinon avec i,j = {1,,52}

35

0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 1 1 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 01 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 0 1 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Documents

Gestion Des Emplois Du Temps