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