Premium
The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options
Author(s) -
Feng Tianke,
Hartman Joseph C.
Publication year - 2015
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.21627
Subject(s) - knapsack problem , postponement , mathematical optimization , markov decision process , computer science , operations research , dynamic programming , queue , decision maker , curse of dimensionality , generalization , stochastic programming , homogeneous , markov process , mathematics , economics , operations management , artificial intelligence , mathematical analysis , statistics , combinatorics , programming language
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