Optimization Online


Formulations for Dynamic Lot Sizing with Service Levels

Dinakar Gade (gade.6***at***osu.edu)
Simge Kucukyavuz (kucukyavuz.2***at***osu.edu)

Abstract: In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal solution to this problem can be found in $\mathcal O(n^2\kappa)$ time, where $n$ is the planning horizon and $\kappa=\mathcal O(n)$ is the maximum number of periods in which demand can be backordered. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS-SL-I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. We show that this relaxation also appears as a substructure in a lot-sizing problem which limits the total amount of a period's demand met from a later period, across all periods. We report computational results that compare the natural and extended formulations on multi-item service-level constrained instances.

Keywords: Fixed-charge networks, lot sizing, service levels, extended formulation, shortest paths

Category 1: Applications -- OR and Management Sciences

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

Category 3: Combinatorial Optimization

Citation: Technical Report, Ohio State University.

Download: [PDF]

Entry Submitted: 12/09/2010
Entry Accepted: 12/09/2010
Entry Last Modified: 05/08/2012

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 Optimization Society