Resource-Constrained Project Scheduling Based on ACO-Critical Chain Method

This paper will present ACO – Critical chain method for scheduling resource-constrained projects. It is based on the critical chain and effective heuristic algorithm method suggested by earlier methods. ACO generates activity lists after searching solution spaces and provides the critical chain used in the chain method. The method then applies both the project buffer and flexible coefficient that adjusts the completed time for the project to more accuracy. The paper also adopts resource utilization change rate to indicate the heuristic information. Two flexible coefficients are given to adjust project completed time.

Resource constrained project scheduling problem (RCPSP) is a generalized class of optimization problem. Its purpose is under the circumstances of the relationship between resource constraints and project tasks, and to minimize a project’s duration by optimizing the schedule and resource allocation. Traditional methods like Design Structure matrix (DSM), Program Evaluation and Review Technique (PERT) and critical path method (CPM) cannot properly run multiple projects simultaneously because they ignore the resource constraint. This method optimizes resource allocation

In RCPSP, suppose a project group has N simultaneous projects with D number of tasks and two virtual activities that do not use time and resources. Then the objective function representing the shortest duration can be shown as: min {max Fi | i 1, 2 … N} (Li, Gong & Kou 486). Fi represents the project completed time.

Ant Colony Optimization (ACO) was initially proposed in the 1990s by Dorigo. It designs virtual ants exploring various routes. Over time, they leave the virtual pheromone’s gradual disappearance. They are able to choose the best route as per the principal of “mutually pheromone closer to line”.  If I is an activity list, in ACO it is constructed by I=(1o,1i….1n+i) (n=∑ni). The activities in ACO are assigned one by one to I from 1o to 1n+I where each assignment symbolizes an ant’s decision. While assigning activity 1r to the r position in I, the Nr set of candidates contains activities with predecessors that are already assigned to the list. As the construction goes on, modification of the Nr set is done step by step. The first ant assigns 10=0 to construct an activity. Then, from the Nr set, the ant selects an activity, say j, and assigns 1r=j from r=1 to r=n. This uses both pheromone and heuristic information. ACO then creates precedence feasible activities. By selecting r-1 activities and scheduling the start times for each, it is then possible to determine the allocated resources and finish times of the activities.

The above descriptions present two problems to be solved by ACO. The first is heuristic significant role played by ACO information, which needs to be expressed. ACO recommends the use of the rate of change of resources utilization to indicate the heuristic information. Secondly, a means must be provided for updating the information. ACO recommends three ways to update information. They are global update, evaporation and local update. Therefore, ACO has several advantages. In the choice of feasible activities, one can choose two types of activities that have the same time. For cut rations, ratios between the lengths of the projects can be used without consideration of the resource constraint and the length of the project using ACO in situations where resources are limited.

Work Cited

  • Li, Kewen, Gong, Lina & Kou, Jisong. Resource-Constrained Project Scheduling Based on           ACO-Critical Chain Method. Shandong: China University of Petroleum & Tianjin           University, 2009. Print.