TY - JOUR
T1 - Optimizing discounted cash flows in project scheduling-an ant colony optimization approach
AU - Chen, Wei Neng
AU - Zhang, Jun
AU - Chung, Henry Shu Hung
AU - Huang, Rui Zhang
AU - Liu, Ou
PY - 2010/1/1
Y1 - 2010/1/1
N2 - The multimode resource-constrained projectscheduling problem with discounted cash flows (MRCPSPDCF) is important and challenging for project management. As the problem is strongly nondeterministic polynomial-time hard, only a few algorithms exist and the performance is still not satisfying. To design an effective algorithm for the MRCPSPDCF, this paper proposes an ant colony optimization (ACO) approach. ACO is promising for the MRCPSPDCF due to the following three reasons. First, MRCPSPDCF can be formulated as a graph-based search problem, which ACO has been found to be good at solving. Second, the mechanism of ACO enables the use of domain-based heuristics to accelerate the search. Furthermore, ACO has found good results for the classical single-mode scheduling problems. But the utility of ACO for the muchmore difficultMRCPSPDCF is still unexplored. In this paper, we first convert the precedence network of the MRCPSPDCF into a mode-on-node (MoN) graph, which becomes the construction graph for ACO. Eight domain-based heuristics are designed to consider the factors of time, cost, resources, and precedence relations. Among these heuristics, the hybrid heuristic that combines different factors together performs well. The proposed algorithm is compared with two different genetic algorithms (GAs), a simulated annealing (SA) algorithm, and a tabu search (TS) algorithm on 55 random instances with at least 13 and up to 98 activities. Experimental results show that the proposed ACO algorithm outperforms the GA, SA, and TS approaches on most cases.
AB - The multimode resource-constrained projectscheduling problem with discounted cash flows (MRCPSPDCF) is important and challenging for project management. As the problem is strongly nondeterministic polynomial-time hard, only a few algorithms exist and the performance is still not satisfying. To design an effective algorithm for the MRCPSPDCF, this paper proposes an ant colony optimization (ACO) approach. ACO is promising for the MRCPSPDCF due to the following three reasons. First, MRCPSPDCF can be formulated as a graph-based search problem, which ACO has been found to be good at solving. Second, the mechanism of ACO enables the use of domain-based heuristics to accelerate the search. Furthermore, ACO has found good results for the classical single-mode scheduling problems. But the utility of ACO for the muchmore difficultMRCPSPDCF is still unexplored. In this paper, we first convert the precedence network of the MRCPSPDCF into a mode-on-node (MoN) graph, which becomes the construction graph for ACO. Eight domain-based heuristics are designed to consider the factors of time, cost, resources, and precedence relations. Among these heuristics, the hybrid heuristic that combines different factors together performs well. The proposed algorithm is compared with two different genetic algorithms (GAs), a simulated annealing (SA) algorithm, and a tabu search (TS) algorithm on 55 random instances with at least 13 and up to 98 activities. Experimental results show that the proposed ACO algorithm outperforms the GA, SA, and TS approaches on most cases.
KW - Ant colony optimization (ACO)
KW - Discounted cash flows
KW - Net present value
KW - Resource-constrained project-scheduling problem (RCPSP)
UR - http://www.scopus.com/inward/record.url?scp=73049110195&partnerID=8YFLogxK
UR - https://ieeexplore.ieee.org/document/5196736
U2 - 10.1109/TSMCC.2009.2027335
DO - 10.1109/TSMCC.2009.2027335
M3 - Article
AN - SCOPUS:73049110195
SN - 1094-6977
VL - 40
SP - 64
EP - 77
JO - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
JF - IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews
IS - 1
M1 - 5196736
ER -