DocumentCode :
2972039
Title :
The stochastic knapsack problem
Author :
Ross, Keith W. ; Tsang, Danny
Author_Institution :
Pennsylvania Univ., Philadelphia, PA, USA
fYear :
1988
fDate :
7-9 Dec 1988
Firstpage :
632
Abstract :
The authors consider a knapsack with integer volume F which is capable of holding K different classes of objects. An object from class-k has integer volume bk, k=1, . . . ,K. Objects arrive randomly to the knapsack; interarrivals are exponential with mean depending on the state of the system. The sojourn time of an object has a general class-dependent distribution. An object in the knapsack from class-k accrues revenue at a rate of rk. The problem is to find a control policy in order to accept/reject the arriving objects as a function of the current state in order to maximize the average revenue. Optimization is carried out over the class of coordinate convex policies. Among other results, for the general case of K classes, the authors consider the problem of finding the optimal static control, where for each class a portion of the knapsack is dedicated
Keywords :
operations research; optimal control; optimisation; stochastic systems; control policy; operations research; optimal control; optimisation; sojourn time; static control; stochastic knapsack problem; stochastic systems; Circuits; Communication channels; Dynamic programming; Facsimile; Heuristic algorithms; Optimal control; Stochastic processes; Stochastic systems; Telecommunication traffic; Traffic control;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 1988., Proceedings of the 27th IEEE Conference on
Conference_Location :
Austin, TX
Type :
conf
DOI :
10.1109/CDC.1988.194387
Filename :
194387
Link To Document :
بازگشت