Resource Allocation, Two-Dimensional Constraints and Discrete Dynamic Programming

摘要

This paper considers the allocation of a scarce resource when the allocation is simultaneously restricted by constraints on two entities, e.g., when both time period and activity constraints are imposed. The major assumption is that return from an allocation to an activity during a single time period is independent of allocations made to the same activity during other time periods or to other activities during the same or other time periods. This two-dimensional resource allocation problem is formulated as a discrete dynamic programming problem, a (0,1) programming problem, and a capacitated transportation problem. The assumptions underlying each formulation are made explicit. Optimal dynamic programming procedures are developed for certain partially constrained forms of the problem and are shown to solve analogous classes of (0,1) programming problems. The general two-dimensional problem remains unsolved; however, an upper bound on the value of the objective function has been found, an iterative search solution procedure has been suggested, and two promising search algorithms are being evaluated. (ERA citation 11:007337)