Ouverture

François Clautiaux (Président de la ROADEF)

Yves Demazeau (Président de l’AFIA)

Zacharie Alès (ROADEF)

Emmanuel Adam (AFIA)

Optimisation des décisions de planification avec coopération entre agents asymétriques dans une chaîne logistique à deux niveaux

Siao-Leu Phouratsamay

(INRIA Bordeaux)

Slides of the presentation

La coordination des décisions opérationnelles d'une chaîne logistique permet d'améliorer sa performance globale ainsi que les objectifs, souvent conflictuels, des entités qui la composent. Dans cet exposé, nous nous intéresserons aux problématiques de coordination des décisions de planification dans le cadre des problèmes de lot-sizing. Nous verrons que dans le contexte des chaînes logistiques à deux acteurs avec monopole, les problèmes issus de cette coordination peuvent se représenter par un jeu avec deux agents asymétriques dans lequel un des agents est forcé de choisir la stratégie qui lui est imposée. Dans un premier temps, une approche basée sur la théorie des contrats sera présentée afin d'inciter les agents à coopérer. Un contrat permet de proposer une stratégie alternative aux agents en optimisant une fonction de choix social et en vérifiant la contrainte dite de rationalité individuelle, aussi connue sous le nom de participation volontaire. Les agents n'ayant pas l'obligation de partager leurs données, la mise en place d'un contrat doit également prendre en compte le manque d'informations sur les données d'un agent. Nous verrons dans un deuxième temps un cas d'étude où déterminer une stratégie alternative optimale nous amènent à étudier de nouvelles classes de problèmes de lot-sizing que nous résolvons par programmation dynamique lorsque ces problèmes sont polynomial.

Planification contingente à l'aide de contre-exemples sur des plans déterministes

Sébastien Piedade

(ONERA Toulouse)

Slides of the presentation

Dans le monde réel, un robot autonome doit prendre en compte les incertitudes de l'environnement lors de ses prises de décision afin de mener à bien sa mission. Dans cette présentation, on propose une nouvelle approche de planification contingente, c'est à dire la planification traitant l'incertitude à propos de l'état initial en incluant des observations de l'environnement. Cette approche contingente utilise un planificateur conformant, c'est à dire un planificateur ne considérant aucune observation, afin de réduire le temps de calcul des plans. Le principe général de notre approche est d'utiliser des contre-exemples retournés par le planificateur conformant lorsqu'aucun plan conformant n'est possible afin de déterminer quelles observations rajouter au plan, et réutiliser le planificateur conformant sur des sous-problèmes avec moins d'incertitude. On évalue notre approche sur un ensemble de benchmarks en comparant ses résultats avec Contingent-FF, un planificateur contingent bien connu.

Pause

Approche décentralisée d’insertion avec amélioration continue de la qualité de la solution pour un système de transport à la demande

Alaa Daoud

(EMSE Saint Etienne)

Slides of the presentation

Pause

The Longest Processing Time rule for identical parallel machines revisited

Federico Della Croce

(Ecole Polytechnique de Turin)

Slides of the presentation

We consider the Pm||Cmax scheduling problem where the goal is to schedule n jobs on m identical parallel machines (m<n) to minimize makespan. We revisit the famous Longest Processing Time (LPT) rule proposed by Graham in 1969. LPT requires to sort jobs in non-ascending order of processing times and then to assign one job at a time to the machine whose load is smallest so far. We provide new insights into LPT and discuss the approximation ratio of a modification of LPT that improves Graham’s bound from 4/3−1/(3m) to 4/3−1/(3(m−1)) for m≥3 and from 7/6 to 9/8 for m=2. We use linear programming to analyze the approximation ratio of our approach. This performance analysis can be seen as a valid alternative to formal proofs based on analytical derivation. Also, we derive from the proposed approach an O(nlogn) time complexity heuristic. The heuristic splits the sorted job set in tuples of m consecutive jobs (1,...,m;m+1,...,2m; etc.) and sorts the tuples in non-increasing order of the difference (slack) between largest job and smallest job in the tuple. Then, given this new ordering of the job set, list scheduling is applied. This approach strongly outperforms LPT on benchmark literature instances and is competitive with more involved approaches such as COMBINE and LDM.

Problème d’affectation dynamique des emplacements de stockage chez Knapp

Paul Courtin

(Knapp Angers)

Slides of the presentation

L’optimisation des performances de préparation des entrepôts automatisés passe par une affection judicieuse des produits aux emplacements de stockage. Ce problème d’affectation des positions de stockage (SLAP), est généralement abordé par les méthodes relevant de la recherche opérationnelle. Nos travaux dressent un état de l’art de cette problématique en soulignant les liens possibles avec l’apprentissage automatique, et des perspectives envisageables de résolution combinant apprentissage automatique et recherche opérationnelle. Nous allons présenter le contexte industriel de Knapp et contexte académique du SLAP. Puis nous verrons comment la RO nous permet de formaliser le problème. Ensuite, nous verrons que nous apporte l’apprentissage automatique.

Discussion

Clôture