Français Anglais
Accueil Annuaire Plan du site
Accueil > Production scientifique > Thèses et habilitations
Production scientifique
Doctorat de GICQUEL Céline
Equipe : Réseaux & Optimisation Combinatoire et Stochastique

MIP models and exact methods for the discrete lot-sizing and scheduling problem with sequence-dependent changeover costs and times

Début le 01/10/2005
Direction :
[Pr M. Minoux et Pr Y. Dallery]

Ecole doctorale : ED STIC 580
Etablissement d'inscription : Centrale Supélec

Lieu de déroulement : Ecole Centrale Paris

Soutenue le 27/10/2008 devant le jury composé de :
Pr M. Gourgand, ISIMA, président
Pr Dauzère-Pérès, Ecole des Mines de Paris, rapporteur
Pr L.A. Wolsey, Université Catholique de Louvain, rapporteur
Pr Y. Dallery, Ecole Centrale Paris, directeur de thèse
Pr M. Minoux, Université de Paris 6, directeur de thèse

Activités de recherche :

Résumé :
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.

Pour en savoir plus: