LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

SOURD Francis

Habilitation
Team : RO

Ordonnancer "Juste-à-temps"

Les travaux présentés dans le cadre de cette habilitation à diriger des recherches concerne les problèmes d'ordonnancement avec des fonctions de coût non monotones (critères ``irréguliers''). Parmi ces problèmes, figurent notamment les problèmes d'ordonnancement ``Juste-à-Temps'' qu'on appelle également les problèmes avec pénalités d'avance et de retard. D'un point de vue théorique, ces problèmes, où sont pénalisés à la fois le retard et l'avance, sont plus complexes que les problèmes dits réguliers, où seul le retard est pénalisé. D'un point de vue pratique, les modèles d'ordonnancement ``Juste-à-Temps'' sont de plus en plus employés dans l'industrie car ces critères permettent entre autres de modéliser relativement simplement à la fois les coûts de stockage et la qualité des livraisons. Le travail effectué s'est basé sur l'étude des problèmes les plus fondamentaux. Les résultats obtenus sur ces problèmes ont été appliqués à la résolution de problèmes plus complexes. En ordonnancement, les deux problèmes de base sont le problème d'ordonnancement de projet (de type PERT) et le problème à une machine. Ces deux problèmes ont été étudiés dans le cadre des critères irréguliers. Notamment, de nouveaux algorithmes polynomiaux ont ainsi été obtenus pour l'ordonnancement de projet avec coûts d'avance et de retard et pour le timing (ordonnancement de séquence) en présence de fonctions de coût linéaire par morceaux. Le problème à une machine étant NP-difficile, différentes études ont porté sur des méthodes de résolution exactes et approchées. On soulignera en particulier que l'introduction et l'amélioration des bornes inférieures ont permis de résoudre des problèmes de 50 à 80 tâches alors que les méthodes précédentes se limitaient aux instances de moins de 20 tâches. Les résultats obtenus sur ces problèmes ont été appliqués à la résolution de problèmes à machines parallèles et aux problèmes d'ordonnancement d'atelier. Ils ont également été généralisés pour intégrer dans les modèles les temps de reconfiguration et les périodes d'indisponibilité. Enfin, un grand travail a été effectué pour modéliser efficacement la préemption, ce qui n'avait jamais été fait dans le cadre des critères irréguliers, et pour développer des algorithmes dédiés. Pour chacun des problèmes étudiés, nous nous sommes efforcé de prouver des nouveaux résultats théoriques et de montrer leur impact et leur efficacité dans la conception et la mise en œuvre de nouveaux algorithmes.
Defence : 04/03/2008 - 14h - Site Passy-Kennedy - salle 549
Jury members :
Jacques Carlier, Université de Technologie de Compiègne
Yves Crama, HEC Management School, University of Liège
Han Hoogeveen, Universiteit Utrecht
Vangelis Paschos, Université Paris Dauphine
Alain Quilliot, ISIMA, Université Blaise Pascal (Clermont-Ferrand II)
Philippe Chrétienne, Université Pierre et Marie Curie
Patrice Perny, Université Pierre et Marie Curie

5 PhD graduated 2005 - 2008

 Mentions légales
Site map |