Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique Soutenance de thèse, Le 16 novembre 2007. Sylvain Bouveret devant le jury composé de : Christian BESSIÈRE, Ulle ENDRISS, Thibault GAJDOS, Jean-Michel LACHIVER (co-directeur de thèse), Jérôme LANG (co-directeur de thèse), Michel LEMAÎTRE (co-directeur de thèse), Patrice PERNY, Thomas SCHIEX Rapporteurs : Boi FALTINGS, Patrice PERNYIntroduction La constellation Pléiades Application CNES Une constellation de satellites agiles d’observation de la Terre en lumière visible haute définition. Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique 2 / 94Introduction La constellation Pléiades Constellation cofinancée de manière inégale par plusieurs pays. Requêtes d’observation... envoyées par chaque agent (agences civiles et militaires de chaque pays) au centre de programmation et de planification, simples (photographie simple acquise en un seul passage) ou complexes (photographies stereo, zones plus larges que le champs de l’instrument optique,...), d’importances inégales pour les agents (idée de préférences). Le centre de programmation et de planification... sélectionne et planifie les prises de vue pour chaque journée, les requêtes ne pouvant pas être toutes réalisées en une journée en raison des contraintes physiques. cette sélection doit satisfaire des contraintes d’équité et d’efficacité (la constellation ne doit pas être ...
Allocation et partage équitables de ressources indivisibles :
modélisation, complexité et algorithmique
Soutenance de thèse, Le 16 novembre 2007.
Sylvain Bouveret
devant le jury composé de :
Christian BESSIÈRE, Ulle ENDRISS, Thibault GAJDOS, Jean-Michel LACHIVER (co-directeur de thèse), Jérôme LANG
(co-directeur de thèse), Michel LEMAÎTRE (co-directeur de thèse), Patrice PERNY, Thomas SCHIEX
Rapporteurs : Boi FALTINGS, Patrice PERNYIntroduction
La constellation Pléiades
Application CNES
Une constellation de satellites agiles d’observation de la Terre en lumière
visible haute définition.
Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique
2 / 94Introduction
La constellation Pléiades
Constellation cofinancée de manière inégale par plusieurs pays.
Requêtes d’observation...
envoyées par chaque agent (agences civiles et militaires de chaque pays) au
centre de programmation et de planification,
simples (photographie simple acquise en un seul passage) ou complexes
(photographies stereo, zones plus larges que le champs de l’instrument
optique,...),
d’importances inégales pour les agents (idée de préférences).
Le centre de programmation et de planification...
sélectionne et planifie les prises de vue pour chaque journée,
les requêtes ne pouvant pas être toutes réalisées en une journée en raison
des contraintes physiques.
cette sélection doit satisfaire des contraintes d’équité et d’efficacité (la
constellation ne doit pas être sous-exploitée).
Comment sélectionner les requêtes de manière à satisfaire les contraintes
physiques et les contraintes d’efficacité et d’équité?
Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique
3 / 94Introduction
La constellation Pléiades
Constellation cofinancée de manière inégale par plusieurs pays.
Requêtes d’observation...
envoyées par chaque agent (agences civiles et militaires de chaque pays) au
centre de programmation et de planification,
simples (photographie simple acquise en un seul passage) ou complexes
(photographies stereo, zones plus larges que le champs de l’instrument
optique,...),
d’importances inégales pour les agents (idée de préférences).
Le centre de programmation et de planification...
sélectionne et planifie les prises de vue pour chaque journée,
les requêtes ne pouvant pas être toutes réalisées en une journée en raison
des contraintes physiques.
cette sélection doit satisfaire des contraintes d’équité et d’efficacité (la
constellation ne doit pas être sous-exploitée).
Comment sélectionner les requêtes de manière à satisfaire les contraintes
physiques et les contraintes d’efficacité et d’équité?
Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique
3 / 94Introduction
La constellation Pléiades
Constellation cofinancée de manière inégale par plusieurs pays.
Requêtes d’observation...
envoyées par chaque agent (agences civiles et militaires de chaque pays) au
centre de programmation et de planification,
simples (photographie simple acquise en un seul passage) ou complexes
(photographies stereo, zones plus larges que le champs de l’instrument
optique,...),
d’importances inégales pour les agents (idée de préférences).
Le centre de programmation et de planification...
sélectionne et planifie les prises de vue pour chaque journée,
les requêtes ne pouvant pas être toutes réalisées en une journée en raison
des contraintes physiques.
cette sélection doit satisfaire des contraintes d’équité et d’efficacité (la
constellation ne doit pas être sous-exploitée).
Comment sélectionner les requêtes de manière à satisfaire les contraintes
physiques et les contraintes d’efficacité et d’équité?
Allocation et partage équitables de ressources indivisibles : modélisation, complexité et algorithmique
3 / 94Le problème de partage...Le problème de partage...
Entrées Un ensemble finiN d’agents .Le problème de partage...
Entrées Un ensemble finiN d’agents .
Une ressource commune limitée.Le problème de partage...
Entrées Un ensemble finiN d’agents .
Une ressource commune limitée.Le problème de partage...
Entrées Un ensemble fini N d’agents exprimant des demandes et des
préférences sur la ressource.
Une ressource commune limitée.
∧ ( ∧ )∨
D E
¬ ∧¬ ,100 ,
D E D E
,20 , ,10
∧ ∧ > ∧ >?