Supervision : Philippe CHRÉTIENNE

Co-supervision : SOURD Francis

Ordonnancement avance-retard sur machines parallèles

La problématique de cette thèse est ``l'ordonnancement avance-retard'': les tâches doivent s'exécuter sur des machines, de telle sorte à minimiser la somme des coûts d'avance et de retard. Ce type de problème est souvent NP-difficile.
Nous définissons un nouveau voisinage de taille exponentielle et proposons un algorithme de programmation dynamique pour déterminer le meilleur ordonnancement du voisinage. Ainsi, une borne supérieure est obtenue pour le cas à une seule date d'échéance commune restrictive.
En résolvant en temps polynomial un problème d'ordonnancement pour lequel les tâches ont des coûts de position, nous proposons une borne inférieure au problème d'ordonnancement juste-à-temps sur machines parallèles identiques.
Finalement, nous proposons une méthode exacte basée sur la relaxation continue de reformulations convexes d'un programme quadratique en 0-1 sous contraintes linéaires.

2004-2008 Publications

• 2008
  • S. Kedad‑Sidhoum, Y. Rios Solis, F. Sourd : “Lower bound for the earliness-tardiness scheduling problem on parallel machines with distinct due dates”, European Journal of Operational Research, vol. 189 (3), pp. 1305-1316, (Elsevier) (2008)
  • Y. Rios Solis, F. Sourd : “Exponential neighborhood search for a parallel machine scheduling problem”, Computers and Operations Research, vol. 35 (5), pp. 1697-1712, (Elsevier) (2008)
• 2007
  • Y. Rios Solis : “Ordonnancement avance-retard sur machines parallèles”, thesis, defence 01/30/2007, supervision Chrétienne, Philippe, co-supervision : Sourd, Francis (2007)
• 2005
  • Y. Rios Solis, F. Sourd : “Parallel scheduling problem with irregular cost functions”, 5^th ALIO/EURO conference on combinatorial optimization, Paris, France, pp. 101-101 (2005)
  • Y. Rios Solis, F. Sourd : “Large neighborhood for a parallel scheduling problem with earliness-tardiness penalties and a common due date”, Multidisciplinary International Conference on Scheduling: Theory and Applications, New York, United States, pp. 169-184 (2005)
  • Y. Rios Solis, F. Sourd : “Voisinage exponentiel pour un problème d’ordonnacement avec des pénalités d’avance-retard autour d’une date d’échéance commune”, 6^e Congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2005), Tours, France, pp. 133-149, (Presses Universitaires François Rabelais) (2005)
• 2004
  • S. Kedad‑Sidhoum, Y. Rios Solis, F. Sourd : “Lower bounds for the earliness-tardiness scheduling problem on parallel machines”, PMS 2004 - 9^th International Workshop on Project Management and Scheduling, Nancy, France, pp. 210-213 (2004)