Wednesday 26
Scheduling, planning and production management
Faiza Sadi
› 11:00 - 11:30 (30min)
› Bât. E - Amphi E
Résolution de problèmes d'ordonnancement intégré de production et de livraison aval de jobs avec dates de début au plus tôt et dates limites de livraison
Liangliang Fu  1@  , Mohamed Ali Aloulou  1@  , Christian Artigues  2@  , Soumaya Bahri  1@  
1 : Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision  (LAMSADE)  -  Website
CNRS : UMR7243, Université Paris IX - Paris Dauphine
Place de Lattre de Tassigny 75775 PARIS CEDEX 16 -  France
2 : Laboratoire d'analyse et d'architecture des systèmes  (LAAS)  -  Website
CNRS : UPR8001, Université Paul Sabatier [UPS] - Toulouse III, Institut National Polytechnique de Toulouse - INPT, Institut National des Sciences Appliquées (INSA) - Toulouse, Institut National des Sciences Appliquées [INSA] - Toulouse
7 Av du colonel Roche 31077 TOULOUSE CEDEX 4 -  France

Nous étudions des problèmes d'ordonnancement intégré de production et de livraison aval d'ordres de fabrication dans un modèle de production à la demande avec un producteur et un client. Dans ce modèle, le producteur reçoit des ordres (ou jobs) du client qui doivent être exécutés sur une seule machine et ensuite livrés par lot au client. Chaque job a une taille unitaire, une date de début au plus tôt , une durée de production et une date limite de livraison. La livraison est réalisée avec des véhicules homogènes de même capacité limitée. Le nombre de véhicules est illimité. La durée et le coût d'une livraison sont indépendants de la constitution du lot. L'objectif est de déterminer un ordonnancement intégré satisfaisant les contraintes de dates limites de livraison et minimisant le coût total de transport.

Nous distinguons trois cas avec différentes propriétés de divisibilité des jobs en production et/ou en livraison : NSP-NSD (i.e. non-splittable production and non-splittable delivery), SP-NSD (i.e. splittable production and non-splittable delivery), SP-SD (i.e. splittable production and delivery). Nous proposons deux algorithmes exacts polynomiaux dans les cas SP-NSD et SP-SD. Nous montrons que le problème dans le cas NSP-NSD est NP-difficile au sens fort et proposons un algorithme exact pour sa résolution. Ce dernier algorithme est en cours d'expérimentation.

Dans la littérature, peu d'articles traitent les problèmes d'ordonnancement intégré de production et de livraison avec des dates de début au plus tôt. La plupart de ces articles considèrent la livraison immédiate et aucun ne prend en compte la divisibilité des jobs en livraison. Aussi le problème avec livraison par lot était ouvert.


Online user: 2