The Dynamic and Stochastic Knapsack Problem with Random Sized Items

Anton J. Kleywegt () and Jason D. Papastavrou ()
Additional contact information
Anton J. Kleywegt: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
Jason D. Papastavrou: School of Industrial Engineering, Purdue University, West Lafayette, Indiana 47907-1287

Operations Research, 2001, vol. 49, issue 1, 26-41

Abstract: A resource allocation problem, called the dynamic and stochastic knapsack problem (DSKP), is studied. A known quantity of resource is available, and demands for the resource arrive randomly over time. Each demand requires an amount of resource and has an associated reward. The resource requirements and rewards are unknown before arrival and become known at the time of the demand's arrival. Demands can be either accepted or rejected. If a demand is accepted, the associated reward is received; if a demand is rejected, a penalty is incurred. The problem can be stopped at any time, at which time a terminal value is received that depends on the quantity of resource remaining. A holding cost that depends on the amount of resource allocated is incurred until the process is stopped. The objective is to determine an optimal policy for accepting demands and for stopping that maximizes the expected value (rewards minus costs) accumulated. The DSKP is analyzed for both the infinite horizon and the finite horizon cases. It is shown that the DSKP has an optimal policy that consists of an easily computed threshold acceptance rule and an optimal stopping rule. A number of monotonicity and convexity properties are studied. This problem is motivated by the issues facing a manager of an LTL transportation operation regarding the acceptance of loads and the dispatching of a vehicle. It also has applications in many other areas, such as the scheduling of batch processors, the selling of assets, the selection of investment projects, and yield management.

Keywords: Dynamic programming/optimal control; Markov: resources allocation; Transportation; scheduling: load acceptance dispatching; Production/scheduling; cutting stock: dynamic stock cutting (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (43)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.1.26.11185 (application/pdf)

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:inm:oropre:v:49:y:2001:i:1:p:26-41

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().