An effective heuristic for the CLSP with set-up times

Abstract

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 (ie. upper bounds) through a smoothing heuristic, followed by a local search with a variable neighbourhood. Solutions found in this way are further 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.

Keywords:

• production
• planning
• networks and graphs
• search
• smoothing heuristic

Acknowledgements

The authors are grateful to Dr W Trigeiro and to Dr M Diaby, each for supplying the source code of his algorithm. They are also grateful to Dr Trigeiro for supplying the data set used for testing.