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

Research

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/Magazine › Journal article › peer-review

Published

Standard

Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic. / Jacko, Peter.
In: Annals of Operations Research, Vol. 241, No. 1, 06.2016, p. 83-107.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Jacko, P 2016, 'Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic', Annals of Operations Research, vol. 241, no. 1, pp. 83-107. https://doi.org/10.1007/s10479-013-1312-9

APA

Jacko, P. (2016). Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic. Annals of Operations Research, 241(1), 83-107. https://doi.org/10.1007/s10479-013-1312-9

Vancouver

Jacko P. Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic. Annals of Operations Research. 2016 Jun;241(1):83-107. Epub 2013 Jan 17. doi: 10.1007/s10479-013-1312-9

Author

Jacko, Peter. / Resource capacity allocation to stochastic dynamic competitors : knapsack problem for perishable items and index-knapsack heuristic. In: Annals of Operations Research. 2016 ; Vol. 241, No. 1. pp. 83-107.

Bibtex

@article{58900c0ee88b41bea6cac340a2170aba,
title = "Resource capacity allocation to stochastic dynamic competitors: knapsack problem for perishable items and index-knapsack heuristic",
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.",
author = "Peter Jacko",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-013-1312-9",
year = "2016",
month = jun,
doi = "10.1007/s10479-013-1312-9",
language = "English",
volume = "241",
pages = "83--107",
journal = "Annals of Operations Research",
issn = "0254-5330",
publisher = "Springer",
number = "1",

}

RIS

TY - JOUR

T1 - Resource capacity allocation to stochastic dynamic competitors

T2 - knapsack problem for perishable items and index-knapsack heuristic

AU - Jacko, Peter

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

PY - 2016/6

Y1 - 2016/6

N2 - 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.

AB - 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.

U2 - 10.1007/s10479-013-1312-9

DO - 10.1007/s10479-013-1312-9

M3 - Journal article

VL - 241

SP - 83

EP - 107

JO - Annals of Operations Research

JF - Annals of Operations Research

SN - 0254-5330

IS - 1

ER -