Tweet
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:
Problème:
Chaque étudiant a au préalable choisi m parmi M unités valeur (matières) disponibles, pour lesquelles (c'est à dire les m matières) il a suivi une formation présentielle ou à distance.
Chaque étudiant doit par la suite passer m examens pour évaluer ses connaissances dans chaque matière optionnelle choisie.
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.
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.
Solution:
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 coloration de graphe ...
Il faut d'abord construire un graphe où les noeuds représente les M matières, ensuite relier chaque couple de noeuds, donc chaque couple de matière m1 et m2, 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 4 couleurs (2 séances de deux heures le matin + 2 séances de 2 heures l'après-midi) et si mon graphe contient 15 noeuds (15 matières ou examens à passer),
je vais procéder comme suit: j'aurais 4 possibilités pour le premier neud, fois 4 possibilités pour le deuxième, ... fois 4 possibilités pour le 15ème.
Ceci fait au total 4*...*4 = 4^15 = 1 073 741 824 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 1 073 741 824 secondes pour trouver une coloration qui marche,
en d'autres termes à peu près 34 ans 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.
Mon problème spécifique se résume sensiblement à ceci:
Problème:
Chaque étudiant a au préalable choisi m parmi M unités valeur (matières) disponibles, pour lesquelles (c'est à dire les m matières) il a suivi une formation présentielle ou à distance.
Chaque étudiant doit par la suite passer m examens pour évaluer ses connaissances dans chaque matière optionnelle choisie.
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.
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.
Solution:
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 coloration de graphe ...
Il faut d'abord construire un graphe où les noeuds représente les M matières, ensuite relier chaque couple de noeuds, donc chaque couple de matière m1 et m2, 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 4 couleurs (2 séances de deux heures le matin + 2 séances de 2 heures l'après-midi) et si mon graphe contient 15 noeuds (15 matières ou examens à passer),
je vais procéder comme suit: j'aurais 4 possibilités pour le premier neud, fois 4 possibilités pour le deuxième, ... fois 4 possibilités pour le 15ème.
Ceci fait au total 4*...*4 = 4^15 = 1 073 741 824 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 1 073 741 824 secondes pour trouver une coloration qui marche,
en d'autres termes à peu près 34 ans 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.
Comment