OPTIMUM SOLUTION OF RESOURCE LEVELING PROBLEM BY COMPLETE ENUMERATION

Önder Halis Bettemir

Abstract:

Solution of resource leveling problem is conducted with meta-heuristic algorithms, mathematical programming, and branch and bound algorithms. However, none of the algorithms can guarantee providing the exact solution of the problem when the number of activities is more than 60. In this study, solution of resource leveling with complete evaluation is implemented and successful results are obtained. The automated complete evaluation process requires automated formation of activity-on-arc type project network; detection of parallel paths and float durations of the activities; formation of schedule combinations by considering the paths and float durations. Activity-on-arc type diagram is formed by implementing the connection of each predecessor with dummy activities and deleting the unnecessary dummies by complete analysis of the network. Activity-on-arc diagram requires less logical checks than activity-on-node type diagram to detect activity clashes due to activity delays. Each path of the network and the critical paths are detected by chaining the nodes of the diagram. The noncritical activities are delayed by nested for loops which are generated automatically according to the number of noncritical activities and the total float durations of the activities. The automated for loops scan the whole search domain of the problem and provide the guaranteed optimum solution. The memory requirement of complete evaluation is within one megabyte since each variable is integer and the whole parameters can be stored at the buffer memory of the central processing unit. This property significantly shortens the computational time for one schedule evaluation compared with population based meta-heuristic algorithms are the buffer memory cannot be adequate and random access memory, which has longer access time, is utilized. Consequently, the complete evaluation process is completed within shorter computation time even tough more schedule evaluations are executed. Moreover, complete evaluation guarantees obtaining the best solution since it evaluates all of the feasible solutions.