کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
476607 | 1446018 | 2014 | 11 صفحه PDF | دانلود رایگان |
• We consider a stochastic knapsack problem with nn types of items and each has infinite supply.
• Stochastic dynamic programming method is applied in evaluating the optimal value function.
• When only two types of items available, there exists an optimal policy.
• A straightforward heuristic policy for general nn gives good performance.
We consider a stochastic knapsack problem in which the event of overflow results in the problem ending with zero return. We assume that there are n types of items available where each type has infinite supply. An item has an exponentially distributed random weight with a known mean depending on its type and the item’s value is proportional to its weight with a given factor depending on the item’s type. We have to make a decision on each stage whether to stop, or continue to put an item of a selected type in the knapsack. An item’s weight is learned when placed to the knapsack. The objective of this problem is to find a policy that maximizes the expected total values. Using the framework of dynamic programming, the optimal policy is found when n=2n=2 and a heuristic policy is suggested for n>2n>2.
Journal: European Journal of Operational Research - Volume 239, Issue 3, 16 December 2014, Pages 625–635