Stochastic Task Selection and Renewable Resource Allocation

This paper studies a class of renewable resource allocation problems for the processing of dynamically arriving tasks with deterministic deadlines. This class of problems has many applications, however, it conforms to neither the standard resource allocation model nor the standard optimal control model. A new problem formulation has to be developed and analyzed to provide a satisfactory solution. In this paper, a new formulation is presented. By augmenting the state variabls, the problem is converted into a Markovian decision problem. It can then be treated, at least in principle, by using the stochastic dynamic programming (SDP) method. However, since the system dynamics involves the evolution of sets (of tasks and resources), the implementation of the dynamic programming equation is by no means straightforward. For a problem with infinite planning horizon, the optimal strategy is shown to be stationary under mild conditions. An SDP algorithm based on a successive approximation technique is developed to obtain the optimal stationary strategy. The implementation of the algorithm employs a special coding scheme to handle set variables, and utilizes a dominance property for computational efficiency. Effects of key system parameters on optimal decisions are investigated and analyzed through numerical examples. As the computational complexity of the algorithm is of exponential increase, practical applications of the algorithm is limited to problems of moderate size. Two heuristic rules are therefore investigated and compared to the optimal policy.