MIP models and exact methods for the Discrete Lot-sizing and Scheduling Problem with sequence-dependent changeover costs and times

Lot-sizing is one of the many issues arising in the context of production planning. Its main objective is to determine the timing and level of production so as to reach the best possible trade-off between minimizing setup and inventory holding costs and satisfying customer demand. When a limited production capacity and a deterministic time-varying demand rate are assumed, lot-sizing leads to the formulation of large-sized mixed-integer programs, most of which are hard to solve.In the present work, we deal with one of the many capacitated dynamic lot-sizing models, the Discrete Lot-sizing and Scheduling Problem or DLSP, and study several variants of this problem where changeover costs and/or times are sequence-dependent. We propose various extensions of an existing exact solution approach for the single-level, single-resource DLSP with sequence-dependent changeover costs.Our contributions concern both problem modelling and efficient implementation of solution algorithms. In terms of problem modelling, we investigate the integration of various additional relevant industrial concerns into the basic model. More precisely, we consider the following operational aspects: the presence of a multi-attribute product structure which can be exploited to reduce the size of the optimization problem, the integration of positive changeover times to better model the production loss caused by a changeover and the presence of identical parallel resources that need to be planned simultaneously. In terms of algorithmic developments, we present for each of these extensions a solution procedure aiming at providing exact optimal solutions: a tight MIP formulation for the corresponding problem variant is derived and the resulting mixed-integer program is solved thanks to a commercial MIP solver. Moreover, results of extensive computational experiments carried out to evaluate the proposed solution approaches are provided. In general, they show the practical usefulness of the proposed algorithms at solving medium to large-sized instances with a reasonable computational effort.Le dimensionnement des lots de production est une des nombreuses activités survenant dans le cadre de la planification de production. Il a pour objet de déterminer quand et combien produire de façon à réaliser le meilleur compromis possible entre la minimisation des coûts liés à la production (coûts fixes de reconfiguration de la ressource, coûts de stockage...) et la satisfaction de la demande des clients Nous nous intéressons ici un problème de planification de production par lots connu sous le nom de "Discrete Lot-sizing and Scheduling Problem" ou "DLSP". Plus précisément, nous étudions plusieurs variantes de ce problème dans lesquelles les coûts et/ou les temps de changement de produits sur la ressource sont dépendant de la séquence et nous proposons diverses extensions d'une méthode disponible dans la littérature pour la résolution exacte du problème mono-niveau, mono-ressource. Nos contributions portent à la fois sur la modélisation du problème et sur l'implémentation de méthodes efficaces de résolution. En ce qui concerne la modélisation, nous étudions l'intégration de divers aspects opérationnels dans le modèle de base afin d'en améliorer la pertinence industrielle. Ainsi nous considérons les extensions suivantes : la prise en compte d'une structure de produits "multi-attributs" qui permet de diminuer la taille du problème d'optimisation à résoudre, l'intégration de temps de changement positifs afin de mieux modéliser la perte de production causée par une reconfiguration de la ressource et la présence de plusieurs ressources parallèles dont la production doit être planifiée simultanément. En ce qui concerne la résolution du problème, nous présentons pour chacune des extensions du modèle de base une approche de résolution visant à fournir des solutions optimales exactes. En général, les résultats de nos expériences numériques montrent l'utilité pratique de ces algorithmes pour la résolution d'instances de moyenne et grande taille en des temps de calcul compatibles avec une application industriell