Integrated production scheduling and delivery routing: complexity results and column generation

Azeddine Cheref (1, 2) , Christian Artigues (2) , Jean-Charles Billaut (1) , Sandra Ulrich Ngueveu (2)

1 LIFAT - Laboratoire d'Informatique Fondamentale et Appliquée de Tours
2 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes

In this paper, we study an integrated production scheduling and delivery routing problem. The manufacturer has to schedule a set of jobs on a single machine without preemption and to deliver them to multiple customers. A single vehicle with limited capacity is used for the delivery. For each job are associated: a processing time, a size and a specific customer location. The problem consists then to determine the production sequence, to constitute batches and to find the best delivery sequence for each batch. The objectives of the proposed problems are to find a coordinated production and a delivery schedule that minimizes the total completion time (makespan) or the sum of the delivery times of the products. We present complexity results for particular cases and a column generation scheme to solve a relaxed version of the problem, leading to a lower bound of high quality. Some computational results show the good performances of the method.

Mots clés: column generation; scheduling; routing

Domaines: Recherche opérationnelle [math.OC]

Azeddine Cheref, Christian Artigues, Jean-Charles Billaut, Sandra Ulrich Ngueveu. Integrated production scheduling and delivery routing: complexity results and column generation. 4th International Symposium on Combinatorial Optimization (ISCO’2016), May 2016, Vietri sur Mare, Italy. ⟨hal-01304786⟩