Article ID: | iaor20073825 |
Country: | United States |
Volume: | 53 |
Issue: | 2 |
Start Page Number: | 281 |
End Page Number: | 297 |
Publication Date: | Mar 2005 |
Journal: | Operations Research |
Authors: | Powell Warren B., Topaloglu Huseyin |
Keywords: | programming: dynamic, programming: assignment |
This paper proposes a distributed solution approach to a certain class of dynamic resource allocation problems and develops a dynamic programming-based multiagent decision-making, learning, and communication mechanism. In the class of dynamic resource allocation problems we consider, a set of reusable resources of different types has to be assigned to tasks that arrive randomly over time. The assignment of a resource to a task removes the task from the system, modifies the state of the resource, and generates a contribution. We build a decision-making scheme where the decisions regarding the resources in different sets of states are made by different agents. We explain how to coordinate the actions of different agents using nonlinear functional approximations, and show that in a distributed setting, nonlinear approximations produce sequences of min-cost network flow problems that naturally yield integer solutions. We also experimentally compare the performances of the centralized and distributed solution strategies.