Discussion :

[mikael71]

Bonsoir,
J'ai longuement hésité avant de poster, pensant y arriver seul, mais là, je suis dans une impasse.

Voici mon problème :
Je cherche à fabriquer une grille d'emploi du temps pour répartir un ensemble d'élèves de terminales pour des oraux blancs sur trois 1/2 journées avec environ 25 profs disponibles.
Je dispose de :
0. de 5 classes (différentes spécialités/options)
1. de 48 groupes formées de 1,2 ou 3 élèves (au total sur les classes)
--> les groupes appartiennent à une classe et passent de 3 à 5 oraux en fonction de leurs spécialités
2. de 25 profs
--> les profs font passer de 1 à 3 classes
--> les profs enseignent une seule matière
--> les oraux durent 20 minutes ou 10 minutes par élève en fonction de la spécialité
3. de 3 * 1/2 journées de 5 heures (disons 13h-18h)

Voici les contraintes :
a. Aucun groupe ne doit passer en même temps 2 matières
b. Certains profs se partagent des classes
c. Un groupe doit impérativement être présent durant les 3 demi-journées.
d. ils doivent tous passer dans leurs matières respectives

Voici "la fonction de coût" :
i. Les profs doivent de préférence travailler sur 2 jours et moins de 4 heures d'affilées
ii. Les profs doivent de préférence commencer en début d'après-midi ou finir par les oraux
iii. Les profs doivent surtout avoir le moins de trous possibles entre les heures (ceci inclut le calcul avec des groupes de 1 ou 2 élèves)
-----------8<--------------------
Compte-tenu de la complexité du problème, j'ai tenté de le résoudre avec un algo génétique.
une grille = 15 x 25 (15 heures / 25 profs)
chaque cellule contient un ou plusieurs groupes

* Je fabrique de manière aléatoire des grilles qui respectent les contraintes (30 grilles environ).
* Je les tris par ordre décroissant de coût
* Je choisis deux grilles pour les faire se reproduire :
-1- en parcourant toute la liste (à partir de 2) avec une proba plus importante de choisir un partenaire antérieur dans la liste
-2- je coupe la grille aléatoirement sur une matière (math / physique ... pas terrible mais je voyais pas comment faire autrement --> non respect des contraintes)
et je mixe les deux grilles pour faire deux enfants qui s'ajoutent à la liste.
-3- j'introduis aléatoirement une mutation en échangeant par prof deux groupes de sorte d'améliorer le cout
* Je retrie la liste et je ne garde que les 30 meilleurs individus.

Je recommence sur plusieurs générations, jusqu'à une solution satisfaisante.
-----------8<--------------------
L'algo fonctionne mais les solutions obtenues ne sont pas "satisfaisantes"
En effet, ainsi, je ne parviens pas à réduire énormément la fonction de cout.

Il est possible que le nombre d'individu initial soit insuffisant et que le nombre de génération le soit aussi. Cependant, je pense que le problème vient davantage de la sélection naturelle et de la création des enfants.

De plus, n'étant pas satisfait, j'ai tenté de passer par une tout autre approche : les systèmes linéaires, voire non linéaires.
Mon problème est l'écriture de la fonction de cout de manière linéaire : je n'y suis pas arrivé.
Pire, je n'arrive pas non plus à fabriquer une fonction différentiable, qui me permettrai d'appliquer un algorithme connu (points intéreiur, simplexe ...)

Mes années de mathématiques appliquées sont assez loin et j'aurais besoin de toute l'aide que vous pourriez me fournir :
* une autre voie : comment feriez vous ?
* des améliorations
* la linéarisation de la fonction de cout

Bref, merci d'avance
Mikaël

[Graffito]

Bonjour,

Le problème n'est pas du tout évident .

Mais, du fait qu'il semble relativement facile de respecter les contraintes, on peut essayer de construire des grilles de départ à priori plus pertinentes.

Voici une idée à ce sujet :

• on peut esssayer de se baser sur un poids pour chaque oral (un éléve, une matière) et un poids pour chaque matière.
• Le poids d'un oral pourrait être obtenu à partir d'une grille aléatoire en calculant le nombre de créneaux disponibles pour un deuxième oral identique (même éléve, même matière).
• Le poids d'une matière serait la somme des poids des oraux pour cette matière.
• Remarque : Si il y a beaucoup d'ex-aequo avec les poids, on peut affiner en faisant une moyenne sur les poids obtenus à partir de plusieurs grilles aléatoires.
• On pourrrait refaire une grille en traitant par priorité les professeur des matières "difficiles" (avec un poids faible) et en remplissant leur emploi du temps en commençant avec les oraux "difficiles" (avec un poids faible)

Dans une matière gérée par plusieurs professeurs, on aura intéret à gèrer un ordre d'affectation dans l'emploi du temps, utillisant une priorité étant définie un peu comme ceci (à approfondir) :
Jx = jour X / Hn = Heure n
Prof1 : j1[H1:H4], j2[H1:H4], j3[H0:H4],j1[H5], j2[H5],j3[H5]
Prof2 : j3[H2:H5], j2[H2:H5], j1[H2:H5],j3[H1], j2[H1],j1[H1]
Prof3 : j2[H1:H4], j3[H1:H4] ...
...

Et sur une plage horaire de priorité identique, on remplira l'emploi du temps du professeur en minimisant les "trous", sans oublier pour les matières avec oraux de 10 minutes de favoriser des plages de 20 minutes complètes.

[mikael71]

Bonjour,
Tout d'abord, merci de t'intéresser à mon problème.

Bonjour,

Le problème n'est pas du tout évident .

Arghh, je m'en doutais ...

Mais, du fait qu'il semble relativement facile de respecter les contraintes, on peut essayer de construire des grilles de départ à priori plus pertinentes.

C'est tout à fait ce que je me suis dit.
J'ai fais diverses tentatives en ce sens.

• choix aléatoire des profs (génération d'une permutation)
• pré-calcul des créneaux disponibles pour cette matière
• l'affectation à un créneau se fait aléatoirement, mais pas uniformément (pour le moment je n'utilisais que la fonction carré pour "tirer" les oraux vers le haut --> alea()^2 [gain de temps], c'était peut-être une erreur)

Du coup il me vient une autre idée : affecter un poids à chaque cellule de sorte que le choix du placement en cours dépende aussi des précédentes affectations ... pour minimiser ce poids !

Si j'ai bien compris ce que tu me proposes, c'est d'affecter un poids par groupe et par matière afin de mieux choisir les matières à traiter en premier. Bonne idée. Je vais tenter cela pour éviter les grilles "impossibles", mais jusqu'à présent (beaucoup de profs volontaires ) il n'y a eu que peu/pas de rejet ...
Peut-être que cela aura aussi pour effet de permettre une meilleure affectation des futurs groupes.

Par contre, tu me parles d'élève/matière, j'imagine que tu parlais de l'entité groupe/matière ?
Le problème principal (et c'est de ma faute j'ai du mal m'expliquer hier) c'est de compresser le planning des profs dans une 1/2journée.

Voici ce que j'ai du mal a éviter :
(G1 est un groupe de 1 élève, G2 est un groupe de 2 élèves et G3 est un groupe de 3 élèves) le tout sur 10 minutes
(avec 4 groupes sur une demi journée G1G2G3G3):
* G1,G2,G3, rien, G3 (coût = 50min+40min+30min+60min+0min)
*-> meilleur choix (G1G2G3, G3 , rien, rien, rien) -> coût=0

Dans une matière gérée par plusieurs professeurs, on aura intéret à gèrer un ordre d'affectation dans l'emploi du temps, utillisant une priorité étant définie un peu comme ceci (à approfondir) :
Jx = jour X / Hn = Heure n
Prof1 : j1[H1:H4], j2[H1:H4], j3[H0:H4],j1[H5], j2[H5],j3[H5]
Prof2 : j3[H2:H5], j2[H2:H5], j1[H2:H5],j3[H1], j2[H1],j1[H1]
Prof3 : j2[H1:H4], j3[H1:H4] ...

Bonne idée !
Pour le moment, je mettais le même poids pour toutes les heures. Je vais essayer comme ça, cela libérera peut-être davantage les créneaux ...

sans oublier pour les matières avec oraux de 10 minutes de favoriser des plages de 20 minutes complètes.

Le truc, c'est que j'avais simplifié avec 10/20 min. Mais certains oraux peuvent être plus exotiques ...

En tout cas merci pour ces idées, je vais voir comment les mettre en place.
Mikaël

PS :
Juste pour avoir une idée, si on avait modélisé le problème par un système linéaire de contraintes en choisissant comme variables de base les G_ijk (où (i,j) est la position de la grille et k le numéro du groupe) prenant les valeurs 0 et 1 si le groupe est attaché/ou non à cette case.
Etait-il possible de trouver une fonction de coût linéaire voire différentiable pour ce problème ? (les contraintes même nombreuses sont toutes linéaires)
Question subsidiaire : est-il alors raisonnable en terme de temps de calcul de traiter 25*15*48(environ) variables de bases ?

[Graffito]

Par contre, tu me parles d'élève/matière, j'imagine que tu parlais de l'entité groupe/matière ?
Le problème principal (et c'est de ma faute j'ai du mal m'expliquer hier) c'est de compresser le planning des profs dans une 1/2journée.

J'avais bien vu l'objectif, mais un peu zappé la notion de groupes d'éléves (D'ailleurs, à quoi ça sert en pratique ?).

Si tous les élèves d'un groupe ont tous les même matières, groupe/matière et elève/matière seront équivalents pour le calcul de poids. Sinon, le poids du groupe/matière serait le nombre de créneaux différents où chaque élève du groupe passe un nouvel oral dans la matière.

Voici ce que j'ai du mal a éviter :
(G1 est un groupe de 1 élève, G2 est un groupe de 2 élèves et G3 est un groupe de 3 élèves) le tout sur 10 minutes
(avec 4 groupes sur une demi journée G1G2G3G3):
* G1,G2,G3, rien, G3 (coût = 50min+40min+30min+60min+0min)
*-> meilleur choix (G1G2G3, G3 , rien, rien, rien) -> coût=0

Le système de poids et de priorité devrait éviter le problème dans la mesure ooù le groupe 3 sera le plus prioritaire de même qu'on favorise l'absence de trous dans l'établissement de l'emploi du temps.

Une idée peut-être : lorsqu'on remplit l'emploi du temps, i.e. en traitant successivement un groupe/une matière, on évalue le coût de toutes les possibilités et on choisit la meilleure!

[mikael71]

J'avais bien vu l'objectif, mais un peu zappé la notion de groupes d'éléves (D'ailleurs, à quoi ça sert en pratique ?).

A priori à rien sinon à rajouter une certaine complexité
Ceci m'est imposé dans la mesure ou les groupes sont faits en fonctions de leurs LV1 et LV2

Si tous les élèves d'un groupe ont tous les même matières, groupe/matière et elève/matière seront équivalents pour le calcul de poids.

Je ne pense pas car il me semble (mais je me trompe peut-être) qu'il est important de différencier les groupes de 1,2 et 3 élèves pour le calcul des coûts. Ou alors, je n'ai rien compris à ce que tu essayes de faire ...
S'agit-il de :

• fabriquer une grille et de l'améliorer en en créant d'autres grace aux poids affectés aux groupes/matières à chaque fois ?
• fabriquer plusieurs grilles de manière aléatoire (mais pas non plus n'importe comment : en utilisant ton idée plus bas) puis fabriquer des enfants de ces grilles en utilisant les poids ?
• autre ?

Sinon, le poids du groupe/matière serait le nombre de créneaux différents où chaque élève du groupe passe un nouvel oral dans la matière.

Oui, bonne idée ça ... Je vais suivre ton conseil.

Une idée peut-être : lorsqu'on remplit l'emploi du temps, i.e. en traitant successivement un groupe/une matière, on évalue le coût de toutes les possibilités et on choisit la meilleure!

C'est exactement ce que je comptais faire.

Dès que tu m'as guidé vers la méthode à employer (ce n'est pas très clair dans ma tête ), je démarre les tests et je te tiendrai au courant des résultats.

Merci pour le coup de main.
Mikaël

[Graffito]

S'agit-il de :

1. fabriquer une grille et de l'améliorer en en créant d'autres grace aux poids affectés aux groupes/matières à chaque fois ?
2. fabriquer plusieurs grilles de manière aléatoire (mais pas non plus n'importe comment : en utilisant ton idée plus bas) puis fabriquer des enfants de ces grilles en utilisant les poids ?
3. autre ?

Les idées que j'ai exposées précédemment consistaient à :

• à creer une grille 1 de façon aléatoire pour calculer les poids,
• à utiliser ces poids pour générer une grille 2 de bonne qualité.

Ensuite (je n'en avais pas parlé dans mes posts précédents), on peut améliorer la grille 2 par permutations:

• on recalcule les poids sur la grille 2,
• on identifie les oraux pénalisants (exemple : prof1 n'a que 2 oraux qui n'aurait que 2 oraux le jour J3) en commençant par les plus difficiles à recaser (petits poids),
• On traite les oraux "pénalisant" en essayant de les caser sur un créneau plus pertinent, à condition que ce nouveau créneau soit vide ou soit occupé par un oral significativement moins "difficile" à bouger, ce qui engendre un déplacement en cascad. En cas d'échec, on laisse l'oral traité à son horaire initial.

Dans ce traitement, on gère une liste d'oraux à déplacer triée par ordre de difficulté. Au départ, rentrent dans la liste les oraux qu'on identifie comme "pénalisants". Au fur et à mesure du traitement, les oraux à déplacer en cascade entrent dans la liste. Attention à limiter le nombre de cascades, car en cas d'échec d'un oral venant d'une cascade, il faudra annuler le déplacement de celui ayant engendré la cascade.

[mikael71]

Les idées que j'ai exposées précédemment consistaient à :

• à creer une grille 1 de façon aléatoire pour calculer les poids,
• à utiliser ces poids pour générer une grille 2 de bonne qualité.

J'en étais resté à ces deux points et c'est ce que j'ai commencé à implémenter.

Ensuite ...

J'ai lu tous tes conseils et le principe me parait pas mal. Je vais réfléchir à la manière de coder tout ça et je te tiens au courant des résultats dans quelques jours.

Merci encore pour tes idées, remarques et éclaircissements.
A bientôt
Mikaël