Optimisation Horaire

[Darklingg]

Bonjour à tous!

J'essaye de rassembler un maximum de documentation et d'information sur la gestion et l'optimisation des horaires avec plusieurs contraintes, quelles qu'elles soient...

Qqun aurait-il des théories ou des algorithmes à me proposer?

Je sais que le sujet est complexe, j'aimerais simplement qu'il soit possible que les théories puissent être appliquables à l'informatiques!

Merci d'avance pour votre participation...

- Darklingg

[DDlacombine]

Salut,

Que veux-tu dire par gestion et optimisation des horaires ?
Tu veux parler d'un problème style établissement d'un emploi du temps ? de problèmes de plannification de production ? (Flowshop, Pert, Gantt...), autres ?
A quelles théories fais-tu référence?
Pour l'instant, à part dire que des réponses se trouvent en recherche opérationnelle, théorie des graphes, optimisation combinatoire... mais je pense que cela tu le sais déjà.

[Darklingg]

Hello!

Enfait, il s'agit de définir des horaires de cours pour un établissement scolaire en tenant compte de contraintes personnalisables et modifiables.

Je me demande quelle méthode serait la plus adaptée pour écrire un programme capable d'écrire les horaires.

Je m'étais tourné vers la programmation linéaire, mais je risque d'avoir des problèmes de complexité dans les calculs assez vite!

-Darklingg

[camaron]

Envoyé par Darklingg

Hello!

Enfait, il s'agit de définir des horaires de cours pour un établissement scolaire en tenant compte de contraintes personnalisables et modifiables.

Je me demande quelle méthode serait la plus adaptée pour écrire un programme capable d'écrire les horaires.

Je m'étais tourné vers la programmation linéaire, mais je risque d'avoir des problèmes de complexité dans les calculs assez vite!

-Darklingg

Surtout que la programmation linéaire est .... linéaire c'est à dire que tes contraintes doivent pouvoir être décrite sous la forme de fonction linéaire avec des mini et des maxi.

Les plannings ont souvent des contraintes qu'il est difficile de linéariser. En revanche si tu y arrive les algoritmes te donneront trés facilement une solution.

Pour les plannings il y a des logiciels d'ordonnancement qui en utilisant des modèles mathématiques plus ou moins élaborés peuevnt faire de l'optimisation.

Mais de mon avis pour un simple ordonnancement de cours, une visualisation de tes schémas a tester sous la forme d'un diagramme de GANT (sans lien) permet d'ajouter de la puissance à la reflexion de celui qui élabore le planning.

[DDlacombine]

Si le coeur t'en dis, tu peux jeter un oeil du coté de la théorie des graphes.
Les problèmes d'emploi du temps peuvent se ramener aux problèmes de coloration de graphes et du nombre chromatique (NP-difficile).

Pour ce que j'en sais, pas grand chose à vrai dire, on modélise par un graphe d'incompatibilité où les sommets représentent les cours à assurer, et où une arête relie les cours qui sont incompatibles,
les sommets d'une même couleur seront les cours compatibles qui peuvent être affectés à un même créneau horaire.

Du point de vue "informatique", Il existe pas mal de méthodes pour attaquer ce genre de problèmes:
- Heuristique séquentielle: algorithme Dsatur
- Enumération arborescente: méthode backtrack
- recuit simulé, recherche tabou...

Mais, franchement, c'est pas trivial...

Sinon, le bon vieux tableau mural avec petits cartons de couleurs ça marche aussi.

[DDlacombine]

Tu peux aussi essayer la programmation par contraintes qui convient bien pour ce genre de problème. Tu devrais pouvoir trouver des bibliothèques assez facilement sur le net, comme par exemple Functional constraint library 1.1 pour OCAML.

[Darklingg]

D'accord...
Merci beaucoup à vous deux!

Sinon, le bon vieux tableau mural avec petits cartons de couleurs ça marche aussi.

Effectivement... la méthode du tableau est toujours très utile!

Mais elle devient difficile à appliquer avec l'augmentation du nombre d'élèves / de professeur / de cours!

Le but est, justement, de trouver un modèle mathématique pour résoudre le problème!

- Darklingg

[la_christe]

Tout dépend du problème, mais il y a quelques algorithmes classiques dans ce genre d optimisations : l'algo du simplex, ou celui de chaitin lorsque le problème est équivalent à un problème de coloration.

[DDlacombine]

Envoyé par Darklingg

Mais elle devient difficile à appliquer avec l'augmentation du nombre d'élèves / de professeur / de cours!
- Darklingg

N'oublie pas les classes !!!
Si tu as P cours et k classes avec k<P, tu tombes sur un problème d'ordonnancement à ressources cumulatives !
Bon courage...