RIOS SOLIS Yasmin Agueda

Docteur
Équipe : RO
Date de départ : 31/01/2007
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 - 14h - Site Passy-Kennedy - salle 550
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-2012

 Mentions légales
Carte du site |