Duality Approaches to Economic Lot-Sizing Games

• 成果类型: Article
• 署名作者: Chen, Xin; Zhang, Jiawei
• 署名单位: University of Illinois System; University of Illinois Urbana-Champaign; New York University
• 刊物名称: PRODUCTION AND OPERATIONS MANAGEMENT
• ISSN/ISSBN: 1059-1478
• DOI: 10.1111/poms.12542
• 发表日期: 2016
• 页码: 1203-1215
• 关键词: economic lot-sizing problems; cooperative games; cost allocation; core; Duality

摘要

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.