A Primal-Dual Algorithm for Computing a Cost Allocation in the Core of Economic Lot-Sizing Games

We consider the economic lot-sizing game with general concave ordering cost functions. It is well-known that the core of this game is nonempty when the inventory holding costs are linear. The main contribution of this work is a combinatorial, primal-dual algorithm that computes a cost allocation in the core of these games in polynomial time. We also show that this algorithm can be used to compute a cost allocation in the core of economic lot-sizing games with remanufacturing under certain assumptions.


Operations Research Letters. doi:10.1016/j.orl.2012.06.009