Decomposition techniques for temporal resource allocation

We consider the problem of allocating a set of heterogeneous resources with availability constraints to maximize a given value function. The problem arises in a wide variety of military and industrial situations. We formulate the problem as a discrete-state decision process. We consider two instances of the problem that are applicable in situations where persistent coverage over all stages is desired. While we were able to solve the first example using dynamic programming, the computational requirements are significant and not scalable to larger instances. We consider an approximate technique using decomposition combined with dynamic programming. Our experiments show that this approach requires very little computation time and produces near-optimal results for the examples considered.