Economic lot sizing with remanufacturing: Structural properties and polynomial-time heuristics

We consider the economic lot sizing problem with remanufacturing, an NP-hard problem which appears in integrated manufacturing and remanufacturing systems. We identify the network flow structure of the problem and derive important properties of its optimal solution. These properties are used to decompose the problem and to show that the resulting subproblems can be solved in polynomial-time. However, the number of subproblems to be solved is exponential, which we overcome by evaluating a limited set of subproblems such that the overall complexity is kept polynomial. This approach leads to a class of polynomial-time heuristics, where the time complexity depends on how the set of subproblems are chosen and how individual subproblems are solved. As a result, a trade-off can be made between computation time and solution quality. A numerical study, where we compare several heuristics within our class of heuristics, shows that our heuristics provide almost optimal solutions and significantly outperform earlier heuristics.

• View at Publisher
• View at Scopus