An effective heuristic for the Capacitated Lot-sizing Problem with set-up times

The problem of multi-item, single level, capacitated, dynamic lot-sizing with set-up times (CLSP with set-up times) is considered. The difficulty of the problem compared with its counterpart without set-up times is explained. A lower bound on the value of the objective function is calculated by Lagrangian relaxation with subgradient optimisation. During the process, attempts are made to get good feasible solutions (i.e. upper bounds) through a smoothing heuristic, followed by a local search with a variable neighbourhood. Solutions found in this way are futher optimised by solving a capacitated transshipment problem. The paper describes the various elements of the solution procedure and presents the results of extensive numerical experimentation.