probleme d'emploi du temps.

La question :

Bonjour,

Je m'intéresse à l'aspect théorique des algorithmes permettant d'obtenir
un emploi du temps en fonction de contraintes.

J'ai bien trouvé quelques références éparses sur google,
le problème semble NP-complet,
peut se résoudre par le coloriage d'un graphe (cela n'est pas clair pour moi)
ou par de la programmation dynamique.

Quelqu'un a-t-il une référence plus précise récapitulant les
différents aspects de la question ?

Bien cordialement.

F.

Poser votre question sur le forum Programmation

Les 2 réponses :

Oui, dans le cas général, ce sont des problèmes assez difficiles.

précision : le problème est NP-difficile (si...) (NP-complet =
problème de décision uniquement)
or là, en plus de trouver des solutions admissibles (qui peuvent être
en soi un vrai problème...), on essaie souvent de minimiser ou
maximiser un critère (ça peut être le cout salarial, le nombre de
classe, etc etc....)

il y a aussi la programmation par contrainte qui est (doit être ?) pas
mal utilisée.

les problématiques d'emploi du temps sont appelées dans la langue de
Chakespehar : "timetabling problem"

De fait, < timetabling problem filetype:pdf > dans google t'emmène
déjà assez loin dans la lecture. En prenant note des biographies de
fin de papier, tu pourras reprendre les articles fondamentaux. Mais je
sais qu'on y travaille encore beaucoup (France et Italie au moins... )

Hope this help...

Vincent

Bonjour,


Je m'intéresse à l'aspect théorique des algorithmes permettant d'obtenir
un emploi du temps en fonction de contraintes [...]
J'ai bien trouvé quelques références éparses sur google,
le problème semble NP-complet, peut se résoudre par le coloriage d'un graphe
(cela n'est pas clair pour moi)


Le problème de coloriage de graphe consiste à colorier chaque sommet
d'un graphe de façon à ce que deux noeuds reliés par une arête
aient toujours des couleurs différentes. En général on cherche à
minimiser le nombre de couleurs nécessaires.

Maintenant supposons que l'on veuille créer un emploi du temps (pour
les exposés d'une conférence) en minimisant le nombre de périodes
temporelles (jours). On peut associer chaque exposé à un noeud d'un
graphe et à toute contrainte d'incompatibilité [par exemple les
exposés X et Y ne peuvent avoir lieu le même jour] un arc du graphe.
Alors en coloriant les arcs du graphe on obtient bien un emploi du
temps valide.

Cette équivalence entre emploi du temps est à la fois forte (les deux
problèmes sont équivalents du point de vue de la NP-complétude) et
faible (des contraintes raisonnables pour un emploi du temps peuvent
requérir une traduction très très complexe en termes de graphes).

La construction d'emploi du temps est quasiment une discipline à part
entière. Elle utilise tous les outils d'optimisation combinatoire à
sa disposition :
- recherche locale
- heuristiques et métaheuristiques
- programmation linéaire en nombres entiers
- programmation par contraintes
- algorithmes dédiés
mais aussi des méthodes d'aide à la décision, de visualisation, etc.

Il y a des conférences dédiées au sujet par exemple PATAT et de
nombreux ouvrages et articles qui traitent de la question. Les mots
clés 'automated time tabling' devraient fournir des point d'entrée
nombreux dans un moteur de recherche.

Diego Olivier

Poser votre question sur le forum Programmation

Questions similaires :

Idees pour resoudre un probleme

Bonjour, Je recherche une ligne directrice pour trouver un algo efficace pour resoudre le probleme suivant: "Etant donne une liste de rectangles (decrit par leur longueur et leur largeur), trouver un rectangle dont l'aire est la plus petite possible et recouvrant tous les rectangles donnes en...

Petit problème de géographie.

Bonjour. "dvanhee" a écrit dans le message de news J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie constructive... De mémoire: on parcours les points du contour (polygone) en considérant pour chaque nouveau point: - le triangle qu'il forme avec les...

Autre problème graphisme

Bonjour à tous Me revoilà avec un nouveau petit problème : J'ai une image couleur codée sur 24 bits (8 bits pour le Rouge, 8 bits pour le Vert et 8 bits pour le Bleu) Je dois arriver à réduire le nombre de couleurs dans l'image finale car chaque pixel est codé sur un nombre de bits variable de 1 bit...

Génération uniforme de solutions d'un problème NP-difficile

Bonjour, Je veux générer une solution d'un problème NP-difficile avec une probabilité uniforme. Le problème NP-difficile se présente sous la forme d'un vecteur booléen de longueur n vérifiant des contraintes de cardinalité de la forme (x_1 + x_3 + x_6 <= 2, respectivement ==, >=) Comme je ne vois...

problème de 3 couleurs

Bonjour messieurs, Voici un algorithme pour 3 couleurs : Soit G un graphe planaire qui a 3-clique comme clique maximum, on note chaque 3-clique par triangle. G contient plusieurs triangles, placer les un à coter des autres, ou séparer par des arrêts. 1) Zone de colorisation obligatoire simple : Si...