Content area
In this thesis we introduce the dynamic assignment problem, which involves the solution of assignment problems over time with evolving information on the availability of resources and tasks, contributions for assigning them and restrictions on the ability to assign them. This thesis is the first major work on extending the classic assignment problem to a dynamic setting. Since the dynamic assignment problem consists of solving sequences of assignment problems over time it lies at an intersection of both linear and dynamic programming. This thesis is one of the first to work at the confluence of these two fundamental areas of operations research.
We provide a formal model of the dynamic assignment problem. Our model explicitly includes both the physical process (the actual arrivals of resources and tasks to the system) and the information process (knowledge about these arrivals and of properties of resources and tasks). We also derive a number of structural properties of the classic assignment problem and certain types of dynamic assignment problems. These properties help provide insight into the problem class and are used in the design of approximation strategies.
We then introduce an approximation strategy for the value function that produces a computationally tractable algorithm that significantly outperforms simple myopic heuristics. Our algorithmic strategy avoids the state space problems of classical dynamic programming. Techniques from stochastic programming (which use scenarios or cuts based on nested-Benders) lose the natural integrality properties of the assignment problem. Our approach involves solving sequences of assignment problems based on sample realizations.
We also examine the effects of aggregation of resources and tasks on the dynamic assignment problem. Aggregation allows us to use the values of resources and tasks that we already know to help approximate values of resources and tasks which are new to the system. This in turn allows us to apply our value function approximation algorithm to even larger problems. We also develop a version of our algorithm which chooses dynamically an appropriate level of aggregation, and we show that this algorithm outperforms our algorithm in which the level of aggregation is static.