The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options

Tianke Feng and Joseph C. Hartman

Naval Research Logistics (NRL), 2015, vol. 62, issue 4, 267-292

Abstract: This article generalizes the dynamic and stochastic knapsack problem by allowing the decision‐maker to postpone the accept/reject decision for an item and maintain a queue of waiting items to be considered later. Postponed decisions are penalized with delay costs, while idle capacity incurs a holding cost. This generalization addresses applications where requests of scarce resources can be delayed, for example, dispatching in logistics and allocation of funding to investments. We model the problem as a Markov decision process and analyze it through dynamic programming. We show that the optimal policy with homogeneous‐sized items possesses a bithreshold structure, despite the high dimensionality of the decision space. Finally, the value (or price) of postponement is illustrated through numerical examples. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 267–292, 2015

Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.21627

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:62:y:2015:i:4:p:267-292

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().