Premium
Duality Approaches to Economic Lot‐Sizing Games
Author(s) -
Chen Xin,
Zhang Jiawei
Publication year - 2016
Publication title -
production and operations management
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 3.279
H-Index - 110
eISSN - 1937-5956
pISSN - 1059-1478
DOI - 10.1111/poms.12542
Subject(s) - mathematical optimization , computer science , profit (economics) , core (optical fiber) , cooperative game theory , dual (grammatical number) , linear programming , duality (order theory) , integer programming , sizing , strong duality , economic order quantity , game theory , cost allocation , operations research , mathematical economics , optimization problem , mathematics , economics , microeconomics , supply chain , marketing , business , art , telecommunications , literature , accounting , discrete mathematics , visual arts
Sharing common production, resources, and services to reduce cost are important for not for profit operations due to limited and mission‐oriented budget and effective cost allocation mechanisms are essential for encouraging effective collaborations. In this study, we illustrate how rigorous methodologies can be developed to derive effective cost allocations to facilitate sustainable collaborations in not for profit operations by modeling the cost allocation problem arising from an economic lot‐sizing (ELS) setting as a cooperative game. Specifically, we consider the economic lot‐sizing (ELS) game with general concave ordering cost. In this cooperative game, multiple retailers form a coalition by placing joint orders to a single supplier in order to reduce ordering cost. When both the inventory holding cost and backlogging cost are linear functions, it can be shown that the core of this game is non‐empty. The main contribution of this study is to show that a core allocation can be computed in polynomial time under the assumption that all retailers have the same cost parameters. Our approach is based on linear programming (LP) duality. More specifically, we study an integer programming formulation for the ELS problem and show that its LP relaxation admits zero integrality gap, which makes it possible to analyze the ELS game by using LP duality. We show that there exists an optimal dual solution that defines an allocation in the core. An interesting feature of our approach is that it is not necessarily true that every optimal dual solution defines a core allocation. This is in contrast to the duality approach for other known cooperative games in the literature.