IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Comprendre un algorithme d'ordonnancement des examens


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club Avatar de bj303931
    Femme Profil pro
    Étudiant
    Inscrit en
    Février 2016
    Messages
    75
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Alpes Maritimes (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Février 2016
    Messages : 75
    Points : 27
    Points
    27
    Par défaut Comprendre un algorithme d'ordonnancement des examens
    Bonsoir, l'Exam Scheduling Problem reste du chinois pour moi...

    Je ne comprends pas comment ils fonctionne . Donc, il faut faire un graphe pondéré de toutes les tâches, il y a des examens superposables, d'autres non...

    Par exemple considérons 12 examens, le 3,5,4,11,12,6 sont superposables d'un côté, le 1,10 de l'autre et enfin, un dernier groupe, composé du 7,2.

    Cependant, le graphe obtenu relie le 3 et le 10 qui ne sont pas superposables et en me temps le 4 qui est superposable. De plus, dans ce graphe des états sont rajoutés par rapport à la consigne !!! Il y a des times period en +!!!! Et des exams qui manquent Bref, la suite en image...

    Nom : Capture du 2017-09-27 17:06:41.png
Affichages : 508
Taille : 340,4 Ko
    Nom : Capture du 2017-09-27 17:07:06.png
Affichages : 475
Taille : 426,4 Ko

    Le lien pdf: http://nvlpubs.nist.gov/nistpubs/jres/84/jresv84n6p489_A1b.pdf

  2. #2
    Membre actif

    Homme Profil pro
    Étudiant
    Inscrit en
    Août 2017
    Messages
    135
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Août 2017
    Messages : 135
    Points : 283
    Points
    283
    Billets dans le blog
    1
    Par défaut
    Salut,
    je ne suis pas sûr de comprendre ton problème. L'algorithme n'est pas très compliqué. D'abord il cherche les contraintes sur les différents examens, et les différentes périodes.
    Suite à cela, il construit un graphe contenant Ti et Ej qui sont respectivement les examens et les périodes. Il relie toute les périodes ensembles pour qu'elles soient chacune d'une couleur différente. Enfin Ei et Ej sont reliés si et seulement si Ej et Ej ne peuvent pas se dérouler en même temps (ici c'est par exemple le cas de E1 et de E4, mais pas de E1 et E2 qui eux ne sont pas liés.) Les dernières arrêtes à placer sont celles entre les Ti et les Ej selon les contraintes qui ont été observées précédemment, une arrête les relies si et seulement si l'exam Ej ne peux pas se dérouler à l'instant Ti.

    Suite à cette opération, il colore le graphe avec autant de couleur que nécessaire pour arriver à placer tous les éléments à une période précise. Il utilise pour ça l'algorithme RLF qu'il détaille.

    Par soucis de présentation, il réalise 2 fois l'étape pour ne pas avoir un trop groos graphe illisible, il ne manque donc pas d'examen, ils sont juste traités un peu après.
    Il ne rajoute pas de période, c'est simplement que T2 et T4 sont libres de toute contrainte, elles n'apparaissaient pas avant dans le tableau.

    C'est sûrement un peu confus. Mais j'espère que ça t'aidera un peu...

Discussions similaires

  1. Algorithme pour representer des arbres quelconques
    Par yarf dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 21/08/2006, 15h49
  2. Algorithme génétique : représentation des différents éléments
    Par maniaco_jazz dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 04/08/2006, 18h08
  3. [FORMS6i]Ordonnancement des blocs
    Par MomoZeAsticot dans le forum Forms
    Réponses: 2
    Dernier message: 26/07/2006, 17h49
  4. algorithme de compression des data en format PNG
    Par vbany dans le forum Autres éditeurs
    Réponses: 2
    Dernier message: 07/04/2006, 15h08
  5. [C / API32 ] Algorithme d'indexation des couleurs
    Par elf dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 03/08/2005, 04h31

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo