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 teaut, Paul Vignard, Corentin Del’homme, Dan Shao, Zangou Dao, Laurent Miscopein et Daudé Guillaume. Enfin, mes remerciements vont à ma femme My-Dung ainsi qu’à nôtre petite fille Gia-An, qui sont à mes côtés depuis le début et qui m’ont toujours écoutées et accom- pagnées dans cette aventure avec beaucoup de patience et surtout d’amour.
Résumé Nous abordons dans cette thèse des problèmes d’ordonnancement de travaux in- dépendants sur une machine ou sur des machines parallèles. Plus précisément, nous abordons deux catégories de problèmes : 1. les problèmes d’ordonnancement de type juste-à-temps : il s’agit de déterminer un ordonnancement de sorte que les travaux se terminent le plus près possible de leur date de fin souhaitée. On considère le cas où la date de fin souhaitée commune est connue et le cas où elle est à déterminer.
De nouveaux algorithmes exacts sont proposés - gloutons et programmes dynamiques -. Des schémas d’ap- proximation sont élaborés. les problèmes d’ordonnancements de travaux interférants : il s’agit de déterminer un ordonnancement qui permet d’optimiser un critère pour la globalité des tra- vaux à effectuer, sachant que la solution trouvée doit permettre également l’opti- misation d’un autre critère défini uniquement sur un sous-ensemble des travaux. Il s’agit ici d’un nouveau problème d’ordonnancement multicritère, différent de la notion classique, et qui se rapproche des problèmes de type "multi-agent schedu- ling" ou "interfering job sets".
Les approches considérées pour trouver une solution non dominée sont l’approche ε-contrainte, la combinaison linéaire de critères et le goal programming. De nouveaux résultats de complexité sont montrés et des al- gorithmes polynomiaux/pseudo-polynomiaux sont développés pour le calcul de cette solution non dominée. Mots-clés : ordonnancement, une machine, machines parallèles, juste-à-temps, tra- vaux interférants, complexité, programmation dynamique, schéma d’approximation iii Abstract In this thesis we consider scheduling problems of independent jobs on a single ma- chine or on parallel machines. More precisely, we tackle two kinds of problems : 1.
just-in-time scheduling problems : it aims to determine a schedule so that a job completes as close as possible to its due date. We consider the case where the common due date is known and the case where the common due date has to be fixed. New exact algorithms based on greedy algorithms and dynamic program- ming are proposed. Approximation schemes are given.
scheduling problems with interfering jobs : the aim is to determine a schedule that optimizes a criterion for the whole set of jobs and so that the solution optimizes another objective only for a subset of jobs. It is here a new multi-criteria schedu- ling problem, different from the classical notion, which is related to "multi-agent” or to "interfering job sets” scheduling problems. The approaches considered for finding a non-dominated solution are the ε-constraint approach, the linear com- bination of criteria and the goal programming approach. New complexity results are proposed and polynomial/pseudo-polynomial algorithms are developed for the calculation of the non-dominated solution.
Keywords : scheduling, single machine, parallel machines, just-in-time, interfering jobs, complexity, dynamic programming, approximation scheme v Table des matières Introduction générale 1 I Ordonnancement juste-à-temps à date due commune 5 1 Introduction à l’ordonnancement juste-à-temps 7 1.1 Systèmes "Juste-à-temps" .2 Mesurer l’avance/retard d’un travail .3 Mesurer le coût total d’avances et retards des travaux .1 Fonction de coût linéaire continue .4 Dates de fin souhaitée .1 Date de fin commune donnée .2 Famille de dates de fin commune donnée .3 Dates de fin commune contrôlable .4 Dates de fin souhaitées généralisées .5 Complexité et approximation polynomiale .1 Approximation et garanties de performances .2 Schémas d’approximation polynomiaux .6 Problèmes d’ordonnancement Juste-à-temps abordés. 24 2 Retard pondéré avec une date de fin donnée 25 2.2 État de l’art .1 Approximabilité du retard pondéré .2 Remarques sur programme dynamique de Lawler et Moore .3 Problème d’ordonnancement à une seule machine .1 Nouveau programme dynamique .4 Problème d’ordonnancement à machines identiques .1 Programme dynamique pour le cas de machines identiques .2 Extension au cas de machines uniformes. 46 3 Avance et retard pondérés avec dates de fin données 49 3.2 Propriétés pour le cas d’une date de fin souhaitée commune .3 Durées opératoires identiques .1 Une seule machine avec une date de fin souhaitée commune .2 Une seule machine avec deux dates de fin souhaitées .3 Une seule machine avec famille de dates de fin souhaitées .4 Machines uniformes avec famille de dates de fin souhaitées .4 Durées opératoires quelconques .1 PTAS pour le cas d’une seule machine .2 PTAS pour le cas de m machines parallèles identiques. 87 4 Avance et retard pondérés avec dates de fin contrôlables 91 4.1 Quelques notations spécifiques à ce chapitre .2 Durées opératoires identiques .1 Une seule machine avec une seule date de fin souhaitée .2 Machines identiques avec famille de dates de fin souhaitées .3 Machines uniformes avec une seule date de fin souhaitée .3 Durées opératoires quelconques .1 Une seule machine avec une seule date de fin souhaitée .2 Machines parallèles avec une seule date de fin souhaitée.
127 5 Conclusion et perspectives de la première partie 129 II Ordonnancement de travaux interférant indépendants 133 6 Introduction à l’ordonnancement des travaux interférants 135 6.1 Motivation et contexte de travail .2 Brève introduction de l’ordonnancement multi-critère .2 Classes de méthodes de résolution .3 Définition de l’ordonnancement avec des travaux interférants .4 État de l’art .5 Intérêt de l’étude. 146 7 Problème d’ordonnancement à une seule machine 149 7.2 Problèmes résolus en temps polynomial .3 Problèmes NP-difficiles au sens ordinaire .4 Problèmes NP-difficiles au sens fort. 169 8 Problème d’ordonnancement à machines parallèles 171 8.2 Résultats de complexité .4 Algorithme de programmation dynamique .1 Formulation générale de programmation dynamique .2 Une application de la formulation générale .3 Problèmes avec les fonction objectifs ∑ Cj (N1 ) et ∑ Cj (N ) .4 Problèmes avec les fonction objectifs ∑ w j Cj (N1 ) and Cmax (N ) .5 Problèmes avec les fonction objectifs ∑ w j Cj (N ) and Cmax (N1 ) .6 Problèmes avec les fonction objectifs Cmax (N ) et Cmax (N1 ). 180 9 Conclusion et perspectives de la seconde partie 181 Conclusion générale et perspectives 183 Liste des tableaux 1.1 Classification des problèmes d’ordonnancement à affecter date de fin [126] 18 1.2 Tableau de problèmes abordés .1 État de l’art sur la minimisation des retards .2 État de l’art sur la minimisation des retards .3 Durées opératoires, dates de fin souhaitées, et pénalités .1 État de l’art sur la minimisation des avances et des retards .2 Durées opératoires, dates de fin souhaitées, et pénalités d’avance/retard 59 3.3 Durées opératoires et les poids (pénalités d’avance et de retard) des travaux 73 4.1 Problèmes JàT avec affectation de la date de fin souhaitée .2 Performance de la borne inférieure par rapport à une borne supérieure .1 Bilan et perspectives .1 Résultats de complexité de l’ordonnancement multi-agent [121] .1 Ordonnancement avec travaux interférants sur une seule machine [118] 150 8.1 Ordonnancement avec travaux interférants sur machines parallèles.
172 xi Table des figures 1.1 Calcul de l’avance en fonction de date de fin souhaitée .2 Calcul de l’avance en fonction de la promptitude .3 Calcul de l’avance en fonction de date de début souhaitée .4 Calcul du retard .5 Fonction de coût d’avance/retard linéaire et continue .6 Juste-à-temps : critère non-régulièr .1 Cas d’une seule machine - position du nouveau travail en retard .2 Cas d’une seule machine - nouvelle fonction de récurrence .3 Cas d’une seule machine - travail Ji est en avance .4 Cas d’une seule machine - travail Ji est en retard .6 Fonction récurrente du cas de machines parallèles .7 Cas 1 - Ji est en avance sur M1 .8 Cas 2 - Ji est en retard sur M1 .9 Cas 3 - Ji est en avance sur M2 .10 Cas 4 - Ji est en retard sur M2 .11 Algorithme WTP2CDD .12 Algorithme WTQ2CDD .1 Positions des travaux sur une machine avec une date due donnée .2 Matrice des coûts d’affectation des travaux .3 Exemple avec 5 travaux .4 Matrice d’affectation avec 5 travaux .5 Matrice d’affectation avec 5 travaux et (δ1 , δ2 ) = (0, 3) .6 Solution optimale correspondant au Cas (a) .7 Matrice d’affectation avec 5 travaux et (δ1 , δ2 ) = (1, 2) .8 Solution optimale selon le cas (b) .9 Exemple avec temps morts dans [ D0 , D1 ] et ] D1 , D2 ] et après D2 .