Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

HAL Id: tel-00009238 https://tel.archives-ouvertes.fr/tel-00009238 Submitted on

HAL Id: tel-00009238 https://tel.archives-ouvertes.fr/tel-00009238 Submitted on 11 May 2005 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Modelisation et resolution de problemes d’optimisation combinatoire issus d’applications spatiales Catherine Mancel To cite this version: Catherine Mancel. Modelisation et resolution de problemes d’optimisation combinatoire issus d’applications spatiales. Automatique / Robotique. INSA de Toulouse, 2004. Français. tel-00009238 Thèse Préparée au Laboratoire d’Analyse et d’Architecture des Systèmes du CNRS en vue de l’obtention du grade de Docteure de l’Institut National des Sciences Appliquées de Toulouse Spécialité : Systèmes Industriels par Catherine Mancel Ingénieure ISIMA MODÉLISATION ET RÉSOLUTION DE PROBLÈMES D’OPTIMISATION COMBINATOIRE ISSUS D’APPLICATIONS SPATIALES Soutenue le 25 juin 2004 devant le jury : Présidente C. MERCÉ Rapporteurs P. MAHEY P. MICHELON Examinateur N. BATAILLE Directeurs de thèse P. LOPEZ R. VALETTE Invité J.-C. HOCHON Avant-propos Le travail présenté dans ce mémoire a été réalisé au Laboratoire d’Automatique et d’Ana- lyse des Systèmes (LAAS) du CNRS, dans le cadre d’une Convention Industrielle de Formation par la Recherche. Je remercie Messieurs Jean-Claude Laprie et Malik Ghallab, directeurs suc- cesifs du laboratoire pendant mon séjour au LAAS, de m’avoir accueillie dans leur structure. Je remercie également Monsieur Christophe Lansade, alors Directeur Régional de la société IXI, devenue par la suite GFI-Consulting, de m’avoir donné la possibilité d’engager cette thèse CIFRE. Pour l’honneur qu’il me fait d’avoir accepté d’être rapporteur de ma thèse et avant cela, pour m’avoir enseigné mes premiers cours de Recherche Opérationnelle à l’Institut Supérieur d’Informatique, de Modélisation et leurs Applications (ISIMA), je remercie Monsieur Philippe Mahey, Professeur à l’Université de Clermont-Ferrand. Je suis très reconnaissante à Mon- sieur Philippe Michelon, Professeur à l’Université d’Avignon et des Pays de Vaucluse, qui m’a également fait l’honneur d’étudier mes travaux et d’en être rapporteur. J’exprime ma gratitude à Madame Colette Mercé, Professeure à l’Institut National des Sciences Appliquées (INSA) de Toulouse, pour avoir présidé le jury de cette thèse et pour sa lecture attentive de mon manuscrit. Je remercie très sincèrement Monsieur Nicolas Bataille, Ingénieur au Centre National des Études Spatiales (CNES), pour sa participation au jury, mais aussi pour l’intérêt qu’il a porté à mes travaux depuis mon DEA et tout au long de ma thèse, et pour l’aide qu’il m’a apportée dans l’étude de diﬀérentes problématiques liées au domaine spatial. Je tiens à remercier Monsieur Jean-Claude Hochon, mon responsable industriel à GFI- Consulting pendant ces années de thèse, qui, tout en me laissant une grande liberté de travail, s’est toujours montré disponible pour répondre à mes questions. Je veux exprimer ici mon extrême reconnaissance envers mes deux directeurs de thèse, Monsieur Pierre Lopez, Chargé de Recherche au LAAS et Monsieur Robert Valette, Directeur de Recherche au LAAS. Leur compétence, les conseils et critiques dont ils m’ont fait bénéﬁcier, ainsi que leur soutien constant et la disponibilité exemplaire dont ils ont fait preuve à mon égard, pendant toute la durée de ma thèse, m’ont permis de mener ces travaux à leur terme. Je remercie Robert pour sa gentillesse au quotidien et pour s’être toujours attaché à suivre au plus près mon travail, qui pourtant s’est très vite éloigné de ses domaines de prédilection. Je remercie Pierre de m’avoir donné goût à ses domaines de recherche et à son métier lors de mon premier stage au LAAS, puis d’avoir continué à m’encadrer dans ce climat de travail appréciable, à la fois rigoureux et détendu. Notre collaboration a été, pour moi, très formatrice et je souhaite qu’elle puisse se poursuivre encore longtemps. Je n’oublie pas mes collègues et amis du LAAS, qui contribuent par leur bonne humeur, leur sympathie, par leur compétence également, à faire de ce lieu un cadre privilégié de travail et d’échanges. J’adresse une pensée particulière aux doctorantes (et docteure) d’ex-OCSD, avec en tête, Emmanuelle et Stéphanie, dont le soutien moral et logistique, tout particulièrement dans les derniers moments, m’a été très précieux. Je remercie enﬁn, pour l’accueil chaleureux qu’ils m’ont réservé, les membres du Labo- ratoire d’Informatique d’Avignon (LIA), où j’ai passé mes derniers mois de thèse en tant qu’ATER. Je remercie en particulier mes collègues chercheurs opérationnels et optimiseurs, notamment Dominique Feillet qui a consacré du temps à la lecture de certaines parties de mon manuscrit, ainsi que Christian Artigues et Cristian Oliva, dont la présence amicale dans les périodes diﬃciles de rédaction m’a beaucoup aidée. Table des matières Introduction 9 I Applications spatiales et optimisation combinatoire 13 1 Problèmes d’optimisation combinatoire dans les applications spatiales 15 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Problèmes classiques d’optimisation combinatoire . . . . . . . . . . . . . . . . . 15 1.2.1 Problème du sac-à-dos . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.2 Problème d’aﬀectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.3 Problème du voyageur de commerce . . . . . . . . . . . . . . . . . . . . 18 1.2.4 Problème d’ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3 Problèmes d’optimisation combinatoire issus d’applications spatiales . . . . . . 21 1.3.1 Spéciﬁcité des problèmes posés . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.2 Modélisation et résolution : revue des méthodes utilisées . . . . . . . . . 23 1.3.2.1 Heuristiques et algorithmes dédiés . . . . . . . . . . . . . . . . 23 1.3.2.2 Approches par contraintes, méthodes d’Intelligence Artiﬁcielle 25 1.3.2.3 Méthodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.3.2.4 Approches par simulation : utilisation des Réseaux de Petri . . 27 1.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2 Techniques de résolution retenues 31 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2 Propagation de contraintes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.1 Propagation de contraintes temporelles . . . . . . . . . . . . . . . . . . . 32 2.2.1.1 Problèmes temporels simples . . . . . . . . . . . . . . . . . . . 32 2.2.1.2 Problèmes temporels généraux . . . . . . . . . . . . . . . . . . 33 2.2.2 Propagation de contraintes de partage de ressources . . . . . . . . . . . 33 2.2.2.1 Opérations locales, opérations globales . . . . . . . . . . . . . . 34 2.2.2.2 Raisonnement énergétique . . . . . . . . . . . . . . . . . . . . . 34 2.3 Programmation linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.1 Déﬁnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.3.2 Résolution des programmes linéaires . . . . . . . . . . . . . . . . . . . . 39 2.3.2.1 Principaux algorithmes . . . . . . . . . . . . . . uploads/Science et Technologie/ tel-00009238.pdf