Modeling the Capacitated Multi-Level Lot-Sizing Problem under Time-Varying Environments and a Fix-and-Optimize Solution Approach

In this study, we investigated the time-varying capacitated lot-sizing problem under a fast-changing production environment, where production factors such as the setup costs, inventory-holding costs, production capacities, or even material prices may be subject to continuous changes during the entire planning horizon. Traditional lot-sizing theorems and algorithms, which often assume a constant production environment, are no longer fit for this situation. We analyzed the time-varying environment of today's agile enterprises and modeled the time-varying setup costs and the time-varying production capacities. Based on these, we presented two mixed-integer linear programming models for the time-varying capacitated single-level lot-sizing problem and the time-varying capacitated multi-level lot-sizing problem, respectively, with considerations on the impact of time-varying environments and dynamic capacity constraints. New properties of these models were analyzed on the solution's feasibility and optimality. The solution quality was evaluated in terms of the entropy which indicated that the optimized production system had a lower value than that of the unoptimized one. A number of computational experiments were conducted on well-known benchmark problem instances using the AMPL/CPLEX to verify the proposed models and to test the computational effectiveness and efficiency, which showed that the new models are applicable to the time-varying environment. Two of the benchmark problems were updated with new best-known solutions in the experiments.