The stochastic knapsack problem
- 1 July 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 37 (7) , 740-747
- https://doi.org/10.1109/26.31166
Abstract
The problem of packing a knapsack of integer volume F with objects from K different classes to maximize profit is studied. Optimization is carried out over the class of coordinate convex policies. For the case of K=2, it is shown for a wide range of parameters that the optimal control is of the threshold type. In the case of Poisson arrivals and of knapsack and object volumes being integer multiples of each other, it is shown that the optimal policy is always of the double-threshold type. An O(F) algorithm to determine the revenue of threshold policies is also given. For the general case of K classes, the problem of the optimal static control where for each class a portion of the knapsack is dedicated is considered. An efficient finite-stage dynamic programming algorithm for locating the optimal static control is presented. Furthermore, variants of the optimal static control which allow some sharing among classes are also discussed. >Keywords
This publication has 9 references indexed in Scilit:
- Optimal circuit access policies in an ISDN environment: a Markov decision approachIEEE Transactions on Communications, 1989
- A simple technique in Markovian control with applications to resource allocation in communication networksOperations Research Letters, 1986
- Insensitivity of blocking probabilities in a circuit-switching networkJournal of Applied Probability, 1984
- Sharing Memory OptimallyIEEE Transactions on Communications, 1983
- The complexity of selection and ranking in X + Y and matrices with sorted columnsJournal of Computer and System Sciences, 1982
- Blocking in a Shared Resource EnvironmentIEEE Transactions on Communications, 1981
- Optimum Allocation of Servers to Two Types of Competing CustomersIEEE Transactions on Communications, 1981
- Resource Sharing for Efficiency in Traffic SystemsBell System Technical Journal, 1981
- Satellite capacity allocationProceedings of the IEEE, 1977