RIOS SOLIS Yasmin Agueda
Direction de recherche : Philippe CHRÉTIENNE
Co-encadrement : 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.
Soutenance : 30/01/2007
Membres du jury :
M. Jean-Charles BILLAUT (Université François-Rabelais de Tours/Laboratoire d'Informatique) [Rapporteur]
Mme. Marie-Claude PORTMANN (Ecole des Mines de Nancy/ Laboratoire Lorrain de Recherche en Informatique et ses Applications) [Rapporteur]
M. Alain BILLIONNET (Institut d'Informatique d'Entreprise du CNAM/Cédric) [Examinateur]
M. Philippe CHRETIENNE (Univesité Paris 6, LIP6) [Directeur de thèse]
M. Jean-Charles POMEROL (Univesité Paris 6, LIP6) [Examinateur]
M. Alain QUILLIOT (Université Clermont-Ferrand/ISIMA) [Examinateur]
M. Francis SOURD (Univesité Paris 6, LIP6) [Co-directeur de thèse]
Publications 2004-2008
-
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”, thèse, soutenance 30/01/2007, direction de recherche Chrétienne, Philippe, co-encadrement : Sourd, Francis (2007)
-
2005
- Y. Rios Solis, F. Sourd : “Parallel scheduling problem with irregular cost functions”, 5th 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”, 6e 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 - 9th International Workshop on Project Management and Scheduling, Nancy, France, pp. 210-213 (2004)