Home > Research > Publications & Outputs > Resource capacity allocation to stochastic dyna...

Associated organisational unit

Electronic data

  • kppi13_springer_aor_rev2

    Rights statement: The original publication is available at www.link.springer.com

    Submitted manuscript, 812 KB, PDF document

Links

Text available via DOI:

View graph of relations

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
<mark>Journal publication date</mark>06/2016
<mark>Journal</mark>Annals of Operations Research
Issue number1
Volume241
Number of pages15
Pages (from-to)83-107
Publication StatusPublished
Early online date17/01/13
<mark>Original language</mark>English

Abstract

In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.

Bibliographic note

The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-013-1312-9