The dynamic and stochastic knapsack problem with deadlines

The dynamic and stochastic knapsack problem with deadlines

0.00 Avg rating0 Votes
Article ID: iaor1998929
Country: United States
Volume: 42
Issue: 12
Start Page Number: 1706
End Page Number: 1718
Publication Date: Dec 1996
Journal: Management Science
Authors: , ,
Keywords: allocation: resources
Abstract:

In this paper a dynamic and stochastic model of the well-known knapsack problem is developed and analyzed. The problem is motivated by a wide variety of real-world applications. Objects of random weight and reward arrive according to a stochastic process in time. The weights and rewards associated with the objects are distributed according to a known probability distribution. Each object can either be accepted to be loaded into the knapsack, of known weight capacity, or be rejected. The objective is to determine the optimal policy for loading the knapsack within a fixed time horizon so as to maximize the expected accumulated reward. The optimal decision rules are derived and are shown to exhibit surprising behaviour in some cases. It is also shown that if the distribution of the weights is concave, then the decision rules behave according to intuition.

Reviews

Required fields are marked *. Your email address will not be published.