Lagrange Relaxation for the Capacitated Multi-item Lot-Sizing Problem

The capacitated multi-item lot-sizing problem abbreviated as CLSP, is to determine the lot sizes of products in each period in a given planning horizon of finite periods meeting the product demand and resource limits in each period, and minimize the total cost consisting of production, inventory holding, and setup costs. CLSPs are often encountered in industry production settings and thus the solution is significant. In this paper, we propose a Lagrange relaxation (LR) approach for the solution of its. The approach decomposes the CLSP into several uncapacitated single-item lot-sizing problems each of which can be easily solved by dynamic programming. The feasible solutions are achieved by solving the resulting transportation problems with a proposed stepping-stone algorithm and a fix-up procedure. The Lagrange multipliers are updated by using subgradient optimization. Experimental results show that the LR approach explores high-quality solutions and has better applicability compared with other commonly used solution approaches in the literature.