On approximations for multiple multidimensional stochastic knapsacks

Many diverse computer performance applications are often modeled as fundamental resource allocation problems in which multiple resources of various types serve a collection of customers with different requirements on each of the resource types. One such fundamental problem of interest that arises in a wide variety of computer application areas, including resource allocation in computer systems and networks, is the stochastic version of the classical knapsack problem. The stochastic aspects of this problem are particularly important in many computer applications because the service requirements of a customer on each resource are often uncertain until after service is completed, together with inherent variability in these service times, and thus the service requirements need to be modeled by a general probability distribution. Some important instances of the stochastic knapsack problem can be used to study computer scheduling problems in which a subset of computer jobs, each with a known value together with uncertain and variable service requirements represented as random variables with a given probability distribution, must be scheduled on one or more resources by a fixed deadline so as to maximize the total value of the jobs scheduled. The different forms of these stochastic scheduling problems have received a great deal of attention in the research literature; refer to, e.g., [5] and the references provided therein. Several different instances of the stochastic knapsack problem have also received considerable attention in the research literature; e.g., see [3, 2, 1] and their references. To the best of our knowledge, the vast majority of previous work on stochastic knapsack problems has considered a single, one-dimensional knapsack. However, in many computer performance applications, the service of customers must be simultaneously allocated among multiple resources of various types each with their own servicetime probability distributions. One simple example of this is where computer jobs need to be allocated both computing and memory resources at the same time during their execution; of course, similar requirements arise in numerous other computer applications. These requirements can be addressed by considering a multidimensional stochastic knapsack problem, where each dimension represents a different resource type, the size of each dimension represents the amount of available resource of that type, and the resource requirements of each job represent the size of the corresponding item to be placed in the knapsack. Furthermore, many computer performance applications involve multiple instances of these resource types. One simple example of this arises in high-performance computing environments in which the system is comprised of multiple nodes each of which consists of computing resources, memory resources, network communication resources, and so on. These additional requirements can be addressed by considering multiple instances of multidimensional stochastic knapsacks. We therefore investigate a significantly more general class of stochastic knapsack problems than has been previously considered. Each of the items available for allocation and each of the knapsacks into which the items can be placed consist of multiple dimensions, where the size of an item for each dimension is drawn from a general probability distribution and the size of each dimension is fixed for every knapsack. The item size becomes known only after an attempt has been made to allocate the item into one of the knapsacks. A value is associated with each item which is realized upon successfully allocating the item into one of the knapsacks without capacity overflow. The value of the knapsack is the summation of the values of all the items that have been allocated into the knapsack multiplied by a weight which is unique to the knapsack. The overall value of an allocation is the summation of the values of all knapsacks under the allocation. Our objective is to study adaptive and non-adaptive classes of strategies for sequentially allocating a set of items among a collection of knapsacks with respect to maximizing the expected overall value of the allocation, and to establish fundamental properties of these allocation strategies. Among all previous work on stochastic knapsack problems, the recent study of Dean, Goemans and Vondrak [1] is the most closely related to our present study. In fact, the one-dimensional, single knapsack version of our problem is equivalent to the problem considered in [1]. It is important to note, however, that our approach is quite different in a number of fundamental aspects, including the use of martingales, stopping times and other probabilistic structures for the stochastic processes underlying the classes of adaptive and non-adaptive allocation strategies of interest. Moreover, we generalize the formulation, derive a new solution approach and establish new results to address the multiple, multidimensional stochastic knapsack problem. Our results provide improvements over the best known results for the single, one-dimensional stochastic knapsack problem and provide the first set of results for the multiple, multidimensional stochastic knapsack problem. Our formulation of the generalized stochastic knapsack problem is presented next, followed by a summary of some of our main results. Additional technical details and results can be found in [4].