Formulations for dynamic lot sizing with service levels

Dinakar Gade, Simge Kucukyavuz*

*Corresponding author for this work

Research output: Contribution to journalArticle

13 Scopus citations

Abstract

In this article, we study deterministic dynamic lot-sizing problems with a service-level constraint on the total number of periods in which backlogs can occur over a 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 O(n2k) time, where n is the planning horizon and K = O(n) is the maximum number of periods in which demand can be backlogged. 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. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013

Original languageEnglish (US)
Pages (from-to)87-101
Number of pages15
JournalNaval Research Logistics
Volume60
Issue number2
DOIs
StatePublished - Jan 11 2013

Keywords

  • Fixed-charge networks
  • extended formulation
  • lot sizing
  • service levels
  • shortest paths

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Formulations for dynamic lot sizing with service levels'. Together they form a unique fingerprint.

  • Cite this