Title: Metaheuristic for the capacitated lot-sizing problem: a software tool for MPS elaboration

Authors: Michel Gourgand, David Lemoine, Sylvie Norre

Addresses: LIMOS, UMR 6158, CNRS, Blaise Pascal University, Clermont-Ferrand, France. ' LIMOS, UMR 6158, CNRS, Blaise Pascal University, Clermont-Ferrand, France. ' LIMOS, UMR 6158, CNRS, Blaise Pascal University, Clermont-Ferrand, France

Abstract: The master production schedule elaboration plays a major part in tactical planning. Among mathematical models which deal with the tactical planning, a particular one is dedicated to it: the capacitated lot-sizing problem. Literature about its resolution is huge, but few metaheuristics have been developed in order to solve it: we propose to use optimisation methods based on a simulated annealing: the data encoding are based on a production planning matrix and the neighbourhood system is maked up of several possible moves. We also proposed a bi-objective function which integrates logistic costs and an evaluation of the degree of the capacities| temporarily leave the set of feasible solutions in order to escape from local minimas. We have tested our optimisation methods on benchmarks from the literature and some best results are outperformed. These methods have been integrated into a software tool.

Keywords: CLSP; capacitated lot sizing problem; metaheuristics; neighbourhood system; bi-objective function; software tools; MPS; master production schedule; mathematical modelling; simulated annealing; production planning; scheduling.

DOI: 10.1504/IJMOR.2010.035496

International Journal of Mathematics in Operational Research, 2010 Vol.2 No.6, pp.724 - 747

Published online: 30 Sep 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article