[Home bibliotech]
Home > Les thèses en ligne de l'INP

A general framework integrating techniques for scheduling under uncertainty

Bidot, Julien (2005) A general framework integrating techniques for scheduling under uncertainty. (Un cadre général intégrant les techniques d'ordonnancement sous incertitudes.)

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
1.26 Mo

Abstract

Ces dernières années, de nombreux travaux de recherche ont porté sur la planification de tâches et l'ordonnancement sous incertitudes. Ce domaine de recherche comprend un large choix de modèles, techniques de résolution et systèmes, et il est difficile de les comparer car les terminologies existantes sont incomplètes. Nous avons cependant identifié des familles d'approches générales qui peuvent être utilisées pour structurer la littérature suivant trois axes perpendiculaires. Cette nouvelle structuration de l'état de l'art est basée sur la façon dont les décisions sont prises. De plus, nous proposons un modèle de génération et d'exécution pour ordonnancer sous incertitudes qui met en oeuvre ces trois familles d'approches. Ce modèle est un automate qui se développe lorsque l'ordonnancement courant n'est plus exécutable ou lorsque des conditions particulières sont vérifiées. Le troisième volet de cette thèse concerne l'étude expérimentale que nous avons menée. Au-dessus de ILOG Solver et Scheduler nous avons implémenté un prototype logiciel en C++, directement instancié de notre modèle de génération et d'exécution. Nous présentons de nouveaux problèmes d'ordonnancement probabilistes et une approche par satisfaction de contraintes combinée avec de la simulation pour les résoudre. ABSTRACT : For last years, a number of research investigations on task planning and scheduling under uncertainty have been conducted. This research domain comprises a large number of models, resolution techniques, and systems, and it is difficult to compare them since the existing terminologies are incomplete. However, we identified general families of approaches that can be used to structure the literature given three perpendicular axes. This new classification of the state of the art is based on the way decisions are taken. In addition, we propose a generation and execution model for scheduling under uncertainty that combines these three families of approaches. This model is an automaton that develops when the current schedule is no longer executable or when some particular conditions are met. The third part of this thesis concerns our experimental study. On top of ILOG Solver and Scheduler, we implemented a software prototype in C++ directly instantiated from our generation and execution model. We present new probabilistic scheduling problems and a constraintbased approach combined with simulation to solve some instances thereof.

Department:Laboratoire Génie de Production - LGP (Tarbes, France)
Directeur de thèse:Grabot, Bernard
Uncontrolled Keywords:Planification de tâches - Ordonnancement - Incertitudes - Flexibilité - Robustesse - Stabilité - Optimisation combinatoire - Satisfaction de contraintes - Simulation. KEYWORDS : Task Planning - Scheduling - Uncertainty - Flexibility - Robustness - Stability - Combinatorial Optimization - Constraint Satisfaction - Simulation
Subjects:Electrical engineering > Industrial systems
Deposited On:24 March 2006

Archive Staff Only: edit this record


Contacts | Infos légales | Plan du site | Intranet

(c)INP de Toulouse 2012 - Tous droits réservés. -  INP Communication