Dynamic programming approximations for dynamic resource allocation problems.

摘要

In this thesis we develop a general solution methodology for multi-stage resource allocation problems called dynamic resource allocation problems (DRAP), which require integer solutions due to the indivisibility of the resources. A DRAP is characterized by the following: (1) There are multiple resource types which serve as substitutes for each other. (2) Each resource has one state variable associated with it and the state of a resource is modified through assignments to tasks. (3) Resources are indivisible and reusable. (4) Tasks arrive at discrete points in time over a finite horizon length. (5) Each resource can serve one task at a time.; Our solution methodology formulates the DRAP as a dynamic program decomposing it into time stages, replaces the value function with an approximation and iteratively updates the value function approximation using samples of the random quantities. We propose using linear and/or separable, piecewise-linear, concave approximations of the value function. We establish the complexity of the subproblems under different value function approximation strategies. We experimentally show that our approach yields solutions that are very close to the optimal objective value for the deterministic instances. For the stochastic instances, our strategy performs significantly better than the standard rolling horizon procedures.; Furthermore, our approach can be visualized as an approximate solution strategy for any multi-stage stochastic program. We present the application of our dynamic programming approximation approach to stochastic programs. We derive the conditions that should be satisfied by our value function approximations so that we can obtain the optimal solution to the stochastic program in question. We numerically show that our approach provides high quality solutions when compared with the optimal solutions and Benders decomposition-based stochastic programming approaches.; The decision making structure in real world instances of DRAP is essentially decentralized in the sense that the command of the resources in different states is given to different decision agents. We present an alternative dynamic programming formulation of DRAP that mimics this decision making structure. In this case, the value function approximations serve as a communication mechanism between agents that help them to learn the impact of their actions on the other parts of the system.