User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Single item lot-sizing with non-decreasing capacities

Primary tabs

Pochet, Yves [Lhoist] Wolsey, Laurence [UCL]

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 relations and reduces to the (known) convex hull of solutions when the capacities are constant over time. We illustrate the use and potential effectiveness of this improved LP formulation on a few test instances, including instances with and without Wagner-Whitin costs, and with both non-decreasing and arbitrary capacities over time.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès interdit
Publication date 2010
Journal information "Mathematical Programming, Series A" - Vol. 121, no. 1, p. 123-143 (Janvier 2010)
Peer reviewed yes
Publisher Springer (Berlin)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations Lhoist
UCL - EUEN/CORE - Center for operations research and econometrics
Keywords Lot-zizing ; Mixing set relaxation ; Compact reformulation ; Production planning ; Mixed integer programming
Links
  1. Atamtürk A., Munoz J.: A study of the lot-sizing polytope. Math. Program. 99, 443–466 (2004)
  2. Bitran G., Yanasse H.: Computational complexity of the capacitated lot size problem. Manage. Sci. 28, 1174–1186 (1982)
  3. Chung C., Lin M.: An O(T 2) algorithm for the NI/G/NI/ND capacitated single item lot size problem. Manage. Sci. 34, 420–426 (1988)
  4. Conforti M., Di Summa M., Wolsey L.: The mixing set with flows. SIAM J. Discrete Math. 29, 396–407 (2007)
  5. Conforti, M., Wolsey, L.: Compact formulations as a union of polyhedra. Math. Program. 114, 277–289 (2008). doi: 10.1007/s10107-007-0101-0 (2007)
  6. de Farias Jr., I., Zhao, M.: The mixing-mir set with divisible capacities. Math. Program. 115, 73–103 (2008). doi: 10.1007/s10107-007-0140-6 (2007)
  7. Di Summa Marco, Wolsey Laurence A., Lot-sizing on a tree, 10.1016/j.orl.2007.04.007
  8. Florian M., Klein M.: Deterministic production planning with concave costs and capacity constraints. Manage. Sci. 18, 12–20 (1971)
  9. Florian M., Lenstra J.K., Rinnooy Kan H.G.: Deterministic production planning: algorithms and complexity. Manage. Sci. 26, 669–679 (1980)
  10. van Hoesel C., Wagelmans A.: An O(T 3) algorithm for the economic lot-sizing problem with constant capacities. Manage. Sci. 42, 142–150 (1996)
  11. Miller A., Wolsey L.: Tight formulations for some simple MIPs and convex objective IPs. Math. Program. B 98, 73–88 (2003)
  12. Pochet Y.: Valid inequalities and separation for capacitated economic lot-sizing. Oper. Res. Lett. 7, 109–116 (1988)
  13. Pochet Y., Wolsey L.: Lot-sizing with constant batches: formulation and valid inequalities. Math. Oper. Res. 18, 767–785 (1993)
  14. Pochet Y., Wolsey L.: Polyhedra for lot-sizing with Wagner–Whitin costs. Math. Program. 67, 297–324 (1994)
  15. Pochet Y., Wolsey L.: Production Planning by Mixed Integer Programming. Springer Series in Operations Research and Financial Engineering, New York (2006)
  16. Van Vyve M.: Algorithms for single-item lot-sizing problems with constant batch size. Math. Oper. Res. 32, 594–613 (2007)
  17. Van Vyve M.: The continuous mixing polyhedron. Math. Oper. Res. 30, 441–452 (2005)
  18. Van Vyve M.: Linear programming extended formulations for the single-item lot-sizing problem with backlogging and constant capacity. Math. Program. 108, 53–78 (2006)
Bibliographic reference Pochet, Yves ; Wolsey, Laurence. Single item lot-sizing with non-decreasing capacities. In: Mathematical Programming, Series A, Vol. 121, no. 1, p. 123-143 (Janvier 2010)
Permanent URL http://hdl.handle.net/2078.1/28760