Approximation algorithms for perishable inventory systems

Xiuli Chao, Xiting Gong, Cong Shi, Huanan Zhang

Research output: Contribution to journalArticlepeer-review

55 Scopus citations


We develop the first approximation algorithms with worst-case performance guarantees for periodic-review perishable inventory systems with general product lifetime, for both backlogging and lost-sales models. The demand process can be nonstationary and correlated over time, capturing such features as demand seasonality and forecast updates. The optimal control policy for such systems is notoriously complicated, thus finding effective heuristic policies is of practical importance. In this paper, we construct a computationally efficient inventory control policy, called the proportional-balancing policy, for systems with an arbitrarily correlated demand process and show that it has a worst-case performance guarantee less than 3. In addition, when the demands are independent and stochastically nondecreasing over time, we propose another policy, called the dual-balancing policy, which admits a worst-case performance guarantee of 2. We demonstrate through an extensive numerical study that both policies perform consistently close to optimal.

Original languageEnglish (US)
Pages (from-to)585-601
Number of pages17
JournalOperations Research
Issue number3
StatePublished - May 1 2015

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Approximation algorithms for perishable inventory systems'. Together they form a unique fingerprint.

Cite this