The traditional lot-sizing problem is to find the least cost production lot-sizes in several time periods. We consider the lot-sizing model with both capacity constraints and minimum order quantity requirements. We first show that the lot-sizing problem with linear cost functions, general capacities and minimum order quantities is NP hard. We then show that the problem is polynomially solvable in presence of constant capacities and minimum order quantities over a finite planning horizon. We also identify a polynomially solvable case with general minimum order quantities and infinite capacities. In the case of general capacities with the minimum order quantities, and in the presence of linear holding, backlogging, procurement costs, and a possible fixed component, we exhibit a fully polynomial time approximation scheme.
|Original language||English (US)|
|Number of pages||19|
|State||Published - 2011|