Un problème d'ordonnancement de messages : Partie 1 Modélisations ; Partie 2 Approches de résolution

Autor: Amet, Henri, Cohen, Johanne, Deppner, Freddy, Portmann, Marie-Claude, Rousseau, Stéphane
Přispěvatelé: Industrial system modeling, analysis and operation (MACSI), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS)-Université Henri Poincaré - Nancy 1 (UHP)-Université Nancy 2-Institut National Polytechnique de Lorraine (INPL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique de l'Université de Tours, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)
Jazyk: francouzština
Rok vydání: 2005
Předmět:
Zdroj: 6ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision-ROADEF'05
6ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision-ROADEF'05, Laboratoire d'Informatique de l'Université de Tours, Feb 2005, Tours/France, pp.54--57
Popis: On considère un réseau tout optique avec une large bande passante. Les messages échangés dans ce réseau sont décrits par le 5-uple (n° du processeur émetteur, n° du processeur receveur, longueur du message, date de disponibilité, délai). Les messages et le réseau en anneau sont découpés en slot. Les messages utilisent des slots consécutifs sans interruption. A chaque top d'horloge, les messages progressent d'un slot sur le réseau. Le processeur receveur peut simultanément lire le contenu d'un slot qui lui est destiné et écrire le contenu d'un slot d'un autre message. Le problème peut être modélisé comme un flow shop sans attente en anneau (cas particulier de job shop sans attente) ou comme un problème particulier de découpe à deux dimensions ou comme un problème d'ordonnancement multiprocesseur avec contraintes de précédence entre couples d'opérations. Il est NP-difficile. Deux approches de résolution sont proposées. L'une utilise une méthode de décomposition temporelle où les sous-problèmes sont résolus de manière exacte en utilisant un modèle de programmation linéaire en nombres entiers et CPLEX. L'autre utilise des algorithmes génétiques à codage indirect avec générateur de solutions à base d'algorithmes de liste et sélection dynamique automatique des opérateurs génétiques.
Databáze: OpenAIRE
Externí odkaz: