The dynamic and stochastic knapsack Problem with homogeneous‐sized items and postponement options |
| |
| Authors: | Tianke Feng Joseph C Hartman |
| |
| Affiliation: | 1. Department of Industrial and Systems EngineeringUniversity of Florida, Gainesville, FL, U.S.;2. College of EngineeringUniversity of Massachusetts Lowell, Lowell, MA, U.S. |
| |
| 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 |
| |
| Keywords: | sequential decisions dynamic programming Markov processes stochastic model applications |
|
|
