RUNGE Nina

Doutor em PhD
Equipe : RO
Data de partida : 30/09/2008
https://lip6.fr/Nina.Runge

Direção de pesquisa : Philippe CHRÉTIENNE

Co-supervisão£o : SOURD Francis

Problèmes d'ordonnancement avance-retard avec et sans préemption

Les problèmes d'ordonnancement juste-à-temps sur une machine modélisent des problèmes rencontrés dans beaucoup de domaines différents comme la fabrication industrielle ou les processus informatiques. Comme la problématique de ces problèmes est fortement inspirée des besoins de l'industrie, nous proposons des extensions qui permettent de prendre encore mieux en compte les caractéristiques spécifiques de certains problèmes. Plus précisément, dans un premier temps, nous examinons les problèmes dans lesquels les interruptions des tâches sont permises et ensuite, nous introduisons la notion de livraison. Comme les problèmes que nous considérons sont NP-difficiles, nous proposons des algorithmes exacts et des heuristiques. Pour les problèmes préemptifs, la fonction objectif non-préemptif ne peut pas être appliquée. Dans ce contexte, nous étudions un modèle préemptif existant et proposons une borne inférieure, une heuristique ainsi qu'un algorithme exact. Le cas particulier du problème ordonnancement préemptif autour d'une date d'échéance commune est examiné séparément. Nous présentons également un nouveau modèle préemptif avec dates d'échéance distinctes pour lequel un nouvel algorithme de timing et un algorithme de recherche locale permettent de calculer des solutions pour des instances de grande taille plus rapidement. Finalement, nous considérons une extension qui consiste à introduire la notion de dates de livraison. Pour ce nouveau modèle, nous présentons deux bornes inférieures et un algorithme de recherche locale.

Defesas : 22/09/2008

Membros da banca :

DÜRR Christoph, Ecole Polytechnique, Rapporteur
NERON Emmanuel, Université de Tours, Rapporteur
MOUKRIM Aziz, Université de Technologie de Compiègne, Examinateur
MUNIER KORDON Alix, Université Paris 6, Examinateur
VANDERBECK Francois, Université de Bordeaux, Examinateur
CHRETIENNE Philippe, Université Paris 6, Directeur de thèse
SOURD Francis, Universite Paris 6, (Co-)Directeur de thèse

Data de partida : 30/09/2008

Publicações 2006-2009

Mentions légales
Mapa do site