Set partitioning and column generation heuristics for capacitated dynamic lotsizing (Q922926)

Some new algorithms to solve the multi-item single-level lotsizing problem with a single capacity constraint are presented. The problem can be stated as \((1)\quad \min \sum^{N}_{i=1}\sum^{T}_{t=1}s_ iY_{it}+h_ iI_{it}\quad \quad (CLSP)(2)\quad s.t.\quad I_{it- 1}+x_{it}-I_{it}=d_{it}\text{ for all } i,t,(3)\quad \sum^{N}_{i=1}a_ ix_{it}\leq C_ t\text{ for all } t,(4)\quad x_{it}\leq (\sum^{T}_{m=t}d_{it})Y_{it}\text{ for all } i,t,(5)\quad x_{it},\quad I_{it}\geq 0\text{ for all } i,t,(6)\quad Y_{it}\in \{0,1\}\text{ for all } i,t,\)where \(x_{it}\), \(Y_{it}\) are variables denoting production quantities, setups and inventories respectively, \(d_{it}\) denotes demand, \(s_ i\) and \(h_ i\) are the setup and holding cost, \(a_ i\) the capacity available in period t. The objective of the model is to minimize total setup and holding cost (1), without backlogs (2), and without violating the capacity constraint in any one period (3). Constraints (4) enforce a setup for item i in any period with positive production for that item. Most previous research efforts reported in the literature use the single item uncapacitated problem solutions as candidate plans. A different approach is proposed in which candidate plans are also generated by some well-known multi-item capacitated dynamic lotsizing heuristics. The LP relaxation of a set partitioning model is solved and rounded to obtain an integer solution. A number of heuristics are subsequently applied to improve upon this initial solution. Heuristics are also used to convert the possibly fractional solution from the column generation step to a feasible integer one. Computational experience shows that these methods perform best for problems with fewer periods than items, but are quite good on average.