Single item lot-sizing with non-decreasing capacities

Yves Pochet and Laurence Wolsey
Additional contact information
Yves Pochet: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)
Laurence Wolsey: Université catholique de Louvain (UCL). Center for Operations Research and Econometrics (CORE)

No 2007048, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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 non-decreasing and arbitrary capacities over time.

Keywords: lot-sizing; mixing set relaxation; compact reformulation; production planning; mixed integer programming (search for similar items in EconPapers)
Date: 2007-08-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2007.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2007048

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().