A Generalized Stochastic Knapsack Problem with Application in Call Admission Control
Marco Cello, Giorgio Gnecco, Mario Marchese, Marcello Sanguineti · IMT Institutional Repository (IMT School for Advanced Studies Lucca) · 2011
In the classical knapsack problem, a knapsack of capacity C is given, together with K classes of objects. For every k = 1, . . . , K, each object of the class k has a size bk and an associated reward rk. The objects can be placed into the knapsack as long as the sum of their sizes does not exceed the capacity C. The problem consists in placing the objects inside the knapsack so as to maximize the total reward. Among the various extensions to a stochastic framework available in the literature (see, e.g., [7,5,3]), we consider the stochastic knapsack problem proposed in [7]. In such a model, objects belonging to each class become available randomly, according to exponentially-distributed inter-arrivals times with means depending on the class and on the state of the knapsack. Each object has a sojourn time independent from the sojourn times of the other objects and described by a class-dependent distribution. If put into the knapsack, an object from class k generates revenue at a positive rate rk. Let nk ≥ 0 denote the number of objects of class k that are currently inside the knapsack. Then one has the linear constraint