期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2007
卷号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：We consider the single item lot-sizing problem with capacities that are non-decreasing over
time. When the cost function is i) non-speculative or Wagner-Whitin (for instance, constant
unit production costs and non-negative unit holding costs), and ii) the production set-up
costs are non-increasing over time, it is known that the minimum cost lot-sizing problem is
polynomially solvable using dynamic programming.
When the capacities are non-decreasing, we derive a compact mixed integer programming
reformulation whose linear programming relaxation solves the lot-sizing problem to
optimality when the objective function satisfies i) and ii). The formulation is based on
mixing set relaxations and reduces to the (known) convex hull of solutions when the
capacities are constant over time.
We illustrate the use and effectiveness of this improved LP formulation on a new test
instances, including instances with and without Wagner-Whitin costs, and with both nondecreasing
and arbitrary capacities over time.
关键词：lot-sizing, mixing set relaxation, compact reformulation, production planning,
mixed integer programming
