RIOS SOLIS Yasmin Agueda
Forschungsgruppe : RO
Datum, an dem das LIP6 verlassen wurde : 31.01.2007
https://lip6.fr/Yasmin.Rios
Forschungsleitung (Direction de recherche) : Philippe CHRÉTIENNE
Co-Betreuung : 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.
Verteidigung einer Doktorarbeit : 30.01.2007
Mitglieder der Prüfungskommission :
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]