+ Répondre à la discussion
Affichage des résultats 1 à 3 sur 3

Discussion: Problème de Planification d'Examens (Examination Timetabling Problem)

          
  1. #1
    Nouveau
    Date d'inscription
    Apr 2014
    Localisation
    Tunis
    Messages
    67

    Problème de Planification d'Examens (Examination Timetabling Problem)

    J'ai du résoudre ce problème en implémentant un module informatique, permettant de planifier des examens sanctionnant une action de formation continue au sein de ma boite.
    Mon problème spécifique se résume sensiblement à ceci:

    [U][B]Problème:[/B][/U]

    Chaque étudiant a au préalable choisi [B]m[/B] parmi [B]M[/B] unités valeur (matières) disponibles, pour lesquelles (c'est à dire les [B]m[/B] matières) il a suivi une formation présentielle ou à distance.
    Chaque étudiant doit par la suite passer [B]m[/B] examens pour évaluer ses connaissances dans chaque matière optionnelle choisie.

    [B]La question est : quel est le nombre minimal de séances nécessaires pour faire passer tous les examens à tous les étudiants sachant que la durée d'un examen est la même et qu'il est possible de programmer plusieurs examens durant la même séance (on dispose en effet d'un nombre suffisant de salles pour accueillir des examens simultanés) avec la contrainte unique suivante: ne pas programmer deux examens devant être passés par un même étudiant durant la même séance.
    [/B]
    Alors bien entendu le fait de regrouper plusieurs examens durant une même séance, permet d'en finir plus vite avec les examens.
    Le fait d'imposer qu'un étudiant n'ait pas pas à passer deux examens différents durant la même séance est trivial: en effet le clonage humain n'est pas un technique envisageable.

    [U][B]Solution:[/B][/U]

    Ayant déjà un peu expérience avec les problèmes de planification, je me doutais que la solution n'allait pas être triviale, par contre je ne croyais pas que le problème était aussi dur à résoudre
    La technique qui revient est celle de la [I]coloration de graphe[/I] ...
    Il faut d'abord construire un graphe où les noeuds représente les [B]M[/B] matières, ensuite relier chaque couple de noeuds, donc chaque couple de matière [B]m1[/B] et [B]m2[/B], par un arc, si et seulement si, il existe au moins un étudiant qui a choisi m1 et m2 parmi ses matières optionnelles. Au final le graphe illustre les conflits qui existent entre les matières: si un arc relie deux matières, alors les examens pour ces deux matières, ne peuvent pas avoir lieu pendant la même séance.
    Pour résoudre le problème, on doit ensuite étiqueter ("colorer") chaque noeud dans le graphe par une séance ("une couleur"), de manière à ne jamais colorer de la même couleur deux noeuds reliés par un arc, et ce en utilisant un nombre minimum de couleurs (de séances).

    Je ne m'attarderai pas sur les solutions existantes (exactes ou approchées), pour ça google fera largement mieux que moi, mais j'aimerais juste souligner qu'un algorithme basique et intuitif devient très vite inutilisable.

    L'idée basique serait d'essayer un coloriage avec une seule couleur, ensuite avec deux et ainsi de suite jusqu'à trouver le nombre de couleurs qui marche.
    Mais par essayer un coloriage on entend parcourir tous les coloriages possibles ...

    Exemple: Si j'essaie de faire tous les coloriages possibles avec seulement [B]4[/B] couleurs (2 séances de deux heures le matin + 2 séances de 2 heures l'après-midi) et si mon graphe contient [B]15[/B] noeuds ([B]15[/B] matières ou examens à passer),
    je vais procéder comme suit: j'aurais [B]4[/B] possibilités pour le premier neud, fois [B]4[/B] possibilités pour le deuxième, ... fois [B]4[/B] possibilités pour le 15ème.
    Ceci fait au total [B]4*...*4 = 4^15 = 1 073 741 824[/B] possibilités de coloriages !!!
    Ensuite pour chaque possibilité de coloriage, il faut vérifier que les conflits entre matières sont respectés: c'est à dire que deux noeuds reliés par un arc ne sont pas coloriés de la même couleur ...
    Mettons que cette vérification prenne une seconde de temps d'exécution, il nous faudrait donc dans le pire des cas [B]1 073 741 824[/B] [B]secondes[/B] pour trouver une coloration qui marche,
    en d'autres termes à peu près [B]34 ans[/B] de temps d'exécution !!!

    La solution que j'ai finalement retenu est une heuristique (méthode non exacte) qui parcourt les neouds un par un et qui essaie de colorier le noeud courant avec une couleur qui ne soit pas déjà utilisée par un noeud auquel le premier est relié par un arc. Si l'ensemble de couleurs disponibles permet de faire un tel coloriage alors le problème est résolu, sinon il faut rajouter une autre couleur et réessayer.

  2. #2
    Nouveau
    Date d'inscription
    Apr 2014
    Localisation
    Tunis
    Messages
    67
    Citation Envoyé par 1881 Voir le message
    La solution que j'ai finalement retenu est une heuristique (méthode non exacte) qui parcourt les neouds un par un et qui essaie de colorier le noeud courant avec une couleur qui ne soit pas déjà utilisée par un noeud auquel le premier est relié par un arc. Si l'ensemble de couleurs disponibles permet de faire un tel coloriage alors le problème est résolu, sinon il faut rajouter une autre couleur et réessayer.
    Il semblerait que cette méthode soit [U]exacte[/U] et non une heuristique ...
    Le fait qu'elle soit exacte, me gêne un peu dans la mesure où elle dépend quand même de l'ordre de parcours des noeuds, je serais donc tenté de penser que changer l'ordre de parcours des noeuds pourrait donner moins ou plus de couleurs nécessaires pour bien colorier le graphe ...

    En tout cas cette méthode répond correctement à ces deux problèmes:

    [B]Problème 1:[/B]

    http://img15.hostingpics.net/pics/212374wims1.png

    Color 1 for 5 nodes = {0, 2, 4, 6, 8}
    Color 2 for 5 nodes = {1, 3, 5, 7, 9}
    Color 3 for 1 nodes = {10}

    [B]Problème 2:[/B]

    http://img15.hostingpics.net/pics/698151wims2.png

    Color 1 for 6 nodes = {0, 2, 4, 6, 8, 10}
    Color 2 for 5 nodes = {1, 3, 5, 7, 9}

    J'essaie de retrouver la démonstration de l'exactitude de cette méthode (sur le web ou par mes propres moyens) et je la posterai le cas échéant.
    Dernière modification par 1881 ; 11-09-2015 à 22h47. Motif: Images pas nettes ...

  3. #3
    Nouveau
    Date d'inscription
    Apr 2014
    Localisation
    Tunis
    Messages
    67
    Je crois que la démonstration est possible par simple récurrence sur l'ordre (nombre de noeuds) du graphe de conflit. On prend un graphe G d'ordre n+1 et on isole un sous-graphe G' d'ordre n dedans (G'=G\{N}). On suppose que l'algorithme permet de résoudre le problème de planification pour le sous-graphe G', ensuite on discute les différentes solutions possibles pour G en fonction de la solution pour G' et des conflit du noeud N.

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •  

Search Engine Optimization by vBSEO

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38