Improvement to an Existing Multi-Level Capacitated Lot Sizing Problem with Setup Carryover, Backlogging, and Emission Control

Rifat Bin Hasan, University of Windsor


This paper presents a multi-level, multi-item, multi-period capacitated lot-sizing problem. The lot-sizing problem studies can obtain production quantities, setup decisions, and inventory levels in each period fulfilling the demand requirements with limited capacity resources, considering the Bill of Material (B.O.M.) structure while simultaneously minimizing the production, inventory, and machine setup costs. The paper proposes an exact solution to Chowdhury et al. (2018)'s developed model, which considers the backlogging cost, setup carryover & greenhouse gas emission control to its model complexity. The problem contemplates the Dantzig-Wolfe (D.W.) decomposition to decompose the multi-level capacitated problem into a single-item uncapacitated lot-sizing sub-problem. To avoid the infeasibilities of the weighted problem (W.P.), an artificial variable is introduced, and the Big-M method is employed in the D.W. decomposition to produce an always feasible master problem. In addition, Wagner & Whitin's forward recursion algorithm is also incorporated in the solution approach for both end and component items to provide the minimum cost production plan. Introducing artificial variables in the D.W. decomposition method is a novel approach to solving the MLCLSP model. A better performance was achieved regarding reduced computational time (reduced by 50%) and optimality gap (reduced by 97.3%) in comparison to Chowdhury et al. (2018)'s developed model.