RESOURCE-ALLOCATION VIA DYNAMIC-PROGRAMMING IN ACTIVITY NETWORKS

doi:10.1016/0377-2217(93)90177-O

RESOURCE-ALLOCATION VIA DYNAMIC-PROGRAMMING IN ACTIVITY NETWORKS

1993-01-01

77

PRE

AI

E

ELMAGHRABY, SE *

DOI：10.1016/0377-2217(93)90177-O

原文链接

原文求助

摘要

En 中文

We investigate the application of dynamic programming to the problem of resource allocation in a project, with the objective of minimizing the project completion time. We assume that there is a relationship between the amount of the resource allocated to an activity and its duration, which is monotone nonincreasing in its argument. The motivation for this study is the recent development of a procedure which yields the minimum number of nodes to be 'reduced' in the AN. This drastically alters the complexity of the DP approach from O(U(h)) to O(U(c)), where h is the number of 'common' activities and c is the minimum number of 'reduced' nodes since, typically, h >> c. We present and illustrate the DP optimizing procedure, which is easily seen to be still plagued by the 'curse of dimensionality' despite the drastic reduction in complexity mentioned above. We then present an elementary approximating procedure which provides an upper bound on the optimum and is computationally more economical for c greater-than-or-equal-to 3. We illustrate both procedures by a small numerical example. Continuing research is devoted to evaluating the efficacy of the approximating procedure, and investigating other approximations.

Keyword:

ACTIVITY NETWORKS

RESOURCE ALLOCATION

DYNAMIC PROGRAMMING

RESOURCE-ALLOCATION VIA DYNAMIC-PROGRAMMING IN ACTIVITY NETWORKS

摘要

AI总结

期刊

机构

引用论文