A tight formulation for uncapacitated lot-sizing with stock upper bounds

• 成果类型: Article
• 署名作者: Wolsey, Laurence A.
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-0999-1
• 发表日期: 2017
• 页码: 603-609
• 关键词: inventory bounds; time windows; fixed costs; models

摘要

For an n-period uncapacitated lot-sizing problem with stock upper bounds, stock fixed costs, stock overload and backlogging, we present a tight extended shortest path formulation of the convex hull of solutions with O variables and constraints, also giving an O algorithm for the problem. This corrects and extends a formulation in Section 4.4 of our article Lot-sizing with production and delivery time windows, Mathematical Programming A, 107:471-489, 2006, for the problem with just stock upper bounds.