Approximation algorithms for supply chain planning and logistics problems with market choice

• 成果类型: Article
• 署名作者: Geunes, Joseph; Levi, Retsef; Romeijn, H. Edwin; Shmoys, David B.
• 署名单位: Massachusetts Institute of Technology (MIT); State University System of Florida; University of Florida; University of Michigan System; University of Michigan; Cornell University; Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0310-9
• 发表日期: 2011
• 页码: 85-106
• 关键词: lot

摘要

We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost production plan (set of facilities) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility opening and connection) costs. These models capture important aspects of demand shaping within supply chain planning and logistics models. We introduce a general algorithmic framework that leverages existing approximation results for the traditional models to obtain corresponding results for their counterpart models with market choice. More specifically, any LP-based alpha-approximation for the traditional model can be leveraged to a 1/1-e(-1/alpha)-approximation algorithm for the counterpart model with market choice. Our techniques are also potentially applicable to other covering problems.