Economic Lot-sizing with Remanufacturing: Complexity and Efficient Formulations



Within the framework of reverse logistics, we consider a remanufacturer, whose customers’ demand can be fulfilled both from newly produced and remanufactured items. More precisely, we study the classic economic lot-sizing problem that has been extended with a remanufacturing option. In this extended problem, known quantities of used products are returned from customers in each period. These returned products can be remanufactured, so that they are as good as new. In each period, we can choose to set up a process to remanufacture returned products or produce new items. These processes can have separate or joint set-up costs. We can show that both variants belong to the class of NP-hard problems.
Furthermore, we propose and compare several alternative mixed integer programming (MIP) formulations of both problems. Because “natural” lot-sizing formulations provide weak lower bounds, we propose tighter formulations, namely shortest path formulations, a partial shortest path formulation and an adaptation of the (l, S, WW)-inequalities for the classic problem with Wagner-Whitin costs. We test their efficiency on a large number of test data sets and find that, for both problem variants, a (partial) shortest path type formulation performs better than the natural formulation, in terms of both the LP relaxation and MIP computation times. Moreover, this improvement can be substantial.
Contact information:
Dr. F. Sting