Algorithms for the two-stage production-capacitated lot-sizing problem

详细信息    查看全文

• 作者：Hark-Chin Hwang ; Hyun-Soo Ahn ; Philip Kaminsky
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：65
• 期：4
• 页码：777-799
• 全文大小：1,251 KB
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916
• 卷排序：65

文摘

We model the two-stage production-capacitated lot-sizing problem as a concave minimum cost network flow problem and characterize the possible patterns of flow between successive periods in which transportation occurs. We demonstrate that production and transportation decisions can be made based only on the local state of transportation patterns between successive transportation periods. Utilizing this observation together with the insight that it is not necessary to consider transportation decisions between transportation periods, we provide a novel improved \(O(T^6)\) algorithm (where T is the length of the planning horizon). We extend this approach to special cases, and develop an \(O(T^5)\) algorithm for the case with non-speculative costs, and an \(O(T^4)\) algorithm for the case with linear costs.KeywordsLot-sizingProduction capacityInventory and logisticsAlgorithms