Optimization Online


Single Item Lot-Sizing with Nondecreasing Capacities

Yves Pochet(pochet***at***core.ucl.ac.be)
Laurence A. Wolsey(laurence.wolsey***at***uclouvain.be)

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 few 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,

Category 1: Applications -- OR and Management Sciences (Production and Logistics )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Category 3: Combinatorial Optimization (Polyhedra )

Citation: CORE Discussion Paper June 2007/48, Universite catholique de Louvain, 1348 Louvain-la-Neuve, Belgium

Download: [PDF]

Entry Submitted: 08/06/2007
Entry Accepted: 08/06/2007
Entry Last Modified: 08/06/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society