Production Routing with Backlogging: A hybrid solution approach.
Nadjib BRAHIMI, IRCCyN UMR 6597
We present mixed integer linear programming formulations for the production routing problem with backordering (PRP-B) and a new hybrid heuristic to solve the problem. The PRP-B is considered in the context of a supply chain consisting of a production facility with limited production and storage capacities and geographically dispersed points of sale with limited storage capacities. The PRP-B integrates multiple item lot sizing decisions and vehicle routing decisions to the points of sale, where backordering of end customer demands is allowed at a penalty. Two integrated mixed integer programming models are formulated and a solution procedure consisting of a relax-and-fix heuristic combined with a local search algorithm is proposed. The numerical results show that this hybrid heuristic outperforms a state-of-the-art MIP commercial solver, in terms of solution quality and CPU times.
Algorithmes d’approximation pour la gestion de stock dans un réseau de distribution.
Guillaume MASSONNET, LIG UMR 5217
Nous étudions un problème à temps discret NP-difficile, dans lequel un entrepôt central approvisionne plusieurs détaillants faisant face à la demande de leurs clients. Nous introduisons une nouvelle technique de décomposition du problème en sous-systèmes plus simples, faciles à résoudre grâce à des techniques classiques de la littérature. Enfin, nous présentons une méthode de recombinaison originale permettant d’obtenir une politique réalisable pour le problème d’origine à partir des sous-solutions obtenues. L’algorithme ainsi défini peut être adapté à plusieurs extensions du modèle de base incluant des structures de coûts plus générales ou encore offrant la possibilité de servir certaines demandes en retard.
En cours de chargement…
Recharger le document 
Ouvrir dans un nouvel onglet Analyse de stabilité des solutions robustes : Cas des machines parallèles non liées avec durées opératoires incertaines.
Widad NAJI, Marie-Laure ESPINOUSE et Van-Dat CUNG, GSCOP UMR 5272
Dans cet exposé, nous considérons le problème de minimisation du makespan sur machines parallèles non liées avec splitting (Rm/Split/Cmax) sous incertitudes des durées opératoires. Ce problème est polynomial en déterministe et modélisable par un PL [Xing and Zhang 2000]. Cependant, sous incertitudes des durées opératoires, les solutions déterministes peuvent dévier du makespan optimal et générer des ordonnancements avec un mauvais équilibrage de charge [Naji et al. 2015]. Lors de la découverte du scénario réel qui est différent du scénario nominal, le décideur se trouve souvent confronté à deux alternatives :
- appliquer la solution nominale au scénario réel afin de garantir la stabilité du planning malgré la dégradation de la performance ;
- ou s’adapter au nouveau scénario afin d’optimiser la performance malgré les aspects de nervosité qui découleront de cette adaptation (perturbation de fonctions de supports tels que la préparation des ressources et la manutention des jobs).
Nous constaterons sur un exemple simple que la stabilité et la performance sont deux objectifs conflictuels. Ce constat fut révélé plus tôt dans [Wu et al. 1993, Abumaizar and Svetska 1997, Sabuncuoglu and Goren 2009]. L’objectif de cette présentation est donc de proposer une approche purement proactive qui permet d’aider un décideur à concilier les deux objectifs, en choisissant la solution qui optimise la performance sous incertitudes des durées opératoires et ayant au mieux une stabilité de la structure pour éviter les aspects de nervosité. L’approche robuste permet la construction de solutions robustes qui optimisent le makespan (au pire-cas par exemple) pour un ensemble de scenarii décrivant les incertitudes pouvant survenir [Kouvelis and Yu 1997]. Toutefois, ces solutions robustes ne peuvent offrir une garantie de performance en dehors de l’ensemble des scenarii donnés. De plus, la prise en compte de tous les scenarii plausibles est difficile. L’ajout d’un scénario potentiel supplémentaire peut donc engendrer une déviation importante dans les structures des solutions robustes ainsi que leur performance. Par conséquent, il est intéressant d’étudier la stabilité des solutions robustes sous l’impact de scenarii supplémentaires n’appartenant pas aux ensembles de scenarii initiaux. Nous proposons des métriques qui permettent de mesurer la stabilité de la structure et la stabilité des performances des solutions robustes. A cet effet, nous présenterons un algorithme composé de deux modules. Le premier module est un algorithme itératif qui permet de construire un ensemble de solutions robustes. A chaque itération, la taille de l’ensemble d’incertitudes est augmentée par la prise en compte d’un scénario potentiel supplémentaire, et plusieurs solutions robustes qui lui correspondent sont calculées. A la fin de chaque itération, nous sauvegardons les structures et les performances des solutions robustes. Le second module permet de comparer, sur la base de nos métriques définies, la stabilité des solutions robustes issues des ensembles d’incertitudes consécutifs. Nous présenterons les résultats des tests effectués.
1. Abumaizar R. J., Svestka J. A. (1997) Rescheduling job shops under random disruptions. International Journal of Production Research 35(7):2065–2082
2. Kouvelis P., Yu G. (1997) Robust discrete optimization and its applications, vol 14.Springer Science & Business Media
3. Naji W., Espinouse M.-L., Cung V.-D. (2015) Towards a robust scheduling on unrelated parallel machines: A scenarios based approach. In: Modelling, Computation and Optimization in Information Systems and Management Sciences, Springer, pp. 343 –355
4. Sabuncuoglu I., Goren S. (2009) Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research. International Journal of Computer Integrated Manufacturing 22(2):138–15 5.
5. Wu S. D., Storer R. H., Pei-Chann C. (1993) One-machine rescheduling heuristics with efficiency and stability as criteria. Computers & Operations Research 20(1):1–14
6. Xing W., Zhang J. (2000) Parallel machine scheduling with splitting jobs. Discrete Applied Mathematics 103(1):259–269
Planification de ressources de transport sous contraintes : le cas d’une plateforme logistique hospitalière
Quentin LAVAL, LSIS UMR 7296
Ce travail de recherche s’inscrit dans le projet logistique de l’Assistance Publique Hôpitaux de Marseille. En effet l’AP-HM a ouvert une plateforme logistique en avril 2013 afin de centraliser les activités de production de repas, de stérilisation, de stockage de produit hôtelier et de blanchiment de linge. Ces produits finis sont ensuite transportés dans des contenants, grâce à une équipe de transport, vers les quatre centres hospitaliers de Marseille (Hôpital Nord, Hôpital de la Timone, Hôpital de la Conception, Hôpitaux Sud). Après la consommation des produits par les unités de soins, les contenants sales utilisés doivent être rapportés à la plateforme logistique pour qu’ils soient désinfectés et réintégrés dans la boucle de production. Le but de ce travail est de proposer un outil de génération de planning de tournées journalières en vue d’aider l’équipe de régulation des transports pour la gestion des ressources de transport sous contraintes avec des temps de transports variables selon la période de la journée. Les temps variables de transport modélisent les différents taux de congestion quotidien et saisonnier de la circulation marseillaise Ces temps de transport peuvent varier de 10 minutes à 1h15 pour certains hôpitaux. Notre problème est un problème de type CVSP (Crew Vehicle Scheduling Problem) que nous avons modélisé grâce à un réseau de Petri. Notre outil intègre en entrée la liste des contenants à transporter de la plateforme logistique aux sites et inversement, les véhicules disponibles ainsi que les chauffeurs. Les contenants ont une date de mise à disponibilité pour le transport, sont de différentes tailles pour chaque type de flux à transporter et sont totalement hermétiques ce qui permet de transporter différents types de produits dans un même véhicule. Le nombre de contenants propres et le nombre de contenants sales peuvent être différents suivant la gestion des unités de soins et il est possible qu’il y ait des transports à vides dans un sens comme dans l’autre. La plateforme logistique dispose d’un dépôt de véhicules hétérogènes avec deux tailles de caisses différentes. Les véhicules les plus petits sont en priorité destinés aux sites qui ont l’espace de manœuvre le plus restreint. Les chauffeurs travaillent sur une plage de 10 heures en continu. Nous proposons une méthode de résolution séquentielle qui consiste, dans un premier temps, à calculer le nombre de transports donc le nombre de véhicules nécessaires pour transporter la liste des contenants produits. Pour cela nous utilisons un algorithme de Bin Packing de type Best Fit Decreasing. Dans un second temps, nous affectons à ces transports un chauffeur.