Complexité Et Algorithmes Pour L'ordonnancement Multicritere De Travaux Indépendants : Problèmes Juste-À-Temps Et Travaux Interférants :Doctor of Philosophy - Spécialité : Informatique

UNIVERSITÉ FRANÇOIS-RABELAIS

DE TOURS

ÉCOLE DOCTORALE : SANTÉ, SCIENCE, ET TECHNOLOGIES

Laboratoire d’Informatique

THÈSE présentée par :

Nguyen HUYNH TUONG

soutenue le : 17 juin 2009

pour obtenir le grade de : Docteur de l’Université François-Rabelais de Tours

Discipline/Spécialité : INFORMATIQUE

COMPLEXITÉ ET ALGORITHMES POUR L’ORDONNANCEMENT

MULTICRITERE DE TRAVAUX INDÉPENDANTS :

PROBLÈMES JUSTE-À-TEMPS ET TRAVAUX INTERFÉRANTS

THÈSE dirigée par :

SOUKHAL Ameur Maître de conférences, Université François Rabelais de Tours

BILLAUT Jean-Charles Professeur, Université François Rabelais de Tours

RAPPORTEURS :

BAPTISTE Philippe Chargé de Recherche CNRS, HDR (Paris)

CHRÉTIENNE Philippe Professeur, Université Pierre et Marie Curie (Paris VI)

JURY :

AGNETIS Alessandro Professeur, Université de Sienne, Italie

BAPTISTE Philippe Chargé de Recherche CNRS, HDR (Paris)

BILLAUT Jean-Charles Professeur, Université François Rabelais de Tours

CARLIER Jacques Professeur, Université de Technologie de Compiègne

CHRÉTIENNE Philippe Professeur, Université Pierre et Marie Curie (Paris VI)

NERON Emmanuel Professeur, Université François Rabelais de Tours

SOUKHAL Ameur Maître de conférences, Université François Rabelais de Tours

À ma famille : mes parents, ma femme et ma fille

Remerciements

Les travaux réalisés au cours de cette thèse ont été effectués au sein du Laboratoire

d’Informatique de l’Université de François Rabelais de Tours (EA 2101), dans l’équipe

Ordonnancement et Conduite.

Je souhaite tout en premier lieu remercier Ameur Soukhal, Maître de Conférences à

l’Ecole Polytech’Tours, qui a encadré cette thèse. Pendant ces trois années, il a su orien￾ter aux bons moments mes travaux de recherches en me faisant découvrir l’ordonnan￾cement au travers de son regard novateur et critique. Ses conseils et ses commentaires

précieux m’ont permis de surmonter les difficulté et de progresser.

Je tiens à exprimer mes remerciements à Jean-Charles Billaut, Professeur de l’Ecole

Polytech’Tours et également mon directeur de thèse, pour ses encouragements, ses

conseils et sa confiance.

J’adresse tous mes sincères remerciements à Philippe Chrétienne, Professeur de

l’Université Pierre et Marie Curie (Paris VI), et à Philippe Baptiste, Professeur de l’École

Polytechnique (LIX), qui m’ont fait l’honneur d’accepter d’être rapporteurs de mes tra￾vaux.

Mes chaleureux remerciements s’adressent à Jacques Carlier, Professeur de l’Uni￾versité de Technologie de Compiègne d’avoir accepté d’être examinateur et président

du jury.

Je remercie également les autres membres du jury qui ont accepté de juger ce travail :

Alessandro Agnetis, Professeur de l’Université de Siena (Italy) et Emmanuel Néron,

Professeur de l’Université François Rabelais de Tours.

Je remercie le Ministère de l’Éducation et la Recherche pour le financement qui m’a

été accordé pour le bon déroulement de ma thèse.

Plus largement, je voudrais remercier les différentes personnes du Laboratoire d’In￾formatique et du Département Informatique de Polytech’Tours auprès desquelles je

suis souvent venue chercher conseil et avec lesquelles j’ai partagé de très bons mo￾ments, tant pour le travail que pour des instants de détente. Grâce à un partage et une

bonne convivialité entre les membres de l’équipes, j’ai eu l’opportunité d’effectuer ma

thèse dans d’excellente condition. Parmi ceux qui ont contribué à mon travail, je remer￾cie tout spécialement Jean-Louis Bouquard et Vincent T’Kindt pour les conseils scienti￾fiques et leur supports. Dans ces remerciements je n’oublie jamais les autres membres

de l’équipe qui ont fait de mon séjour, une période très agréable et enrichissante. Je

pense en particulier à Christian Proust (Directeur de l’Ecole Polytech’Tours), Patrick

Martineau, Christophe Lenté, Claudine Tacquard, Carl Esswein, Geoffey Vilcot, Cédric

Pessan, Mathieu Pérotin, Cédric Mocquillon, Mathieu Rouleau, Yanick Kergosen, Gaël

Sauvanet, et Rabah Belaid. Mes remerciements sont adressés également aux étudiants

du cycle d’ingénieur qui sont intervenus dans mes projets de recherche : Brien Lit￾i