An Ant Colony Algorithm for Improving the Net Present Values of Resource Constrained Projects

用蟻群演算法改進資源受限專案的淨現值

10.29977/JCIIE.200611.0005

壽湧毅(Yong-Yi Shou)

人工蟻群 ； 資源受限專案 ； 淨現值 ； ant colony ； resource-constrained project ； net present value

工業工程學刊

23卷6期（2006 / 11 / 01）

478 - 483

英文

對於多數工期較長、現金流較大的工程專案而言，淨現值(net present value, NPV)是非常重要的專案管理指標。同時，一般的專案所能調動的資源相當受限，如何合理調配資源，優化工程進度，從而改善專案淨現值，就成為重要的課題。本文提出一種基於人工蟻群(artificial ant colony)的演算法，以改進資源受限專案的淨現值。該演算法根據人工蟻群逐步產生的費洛蒙(pheromone)動態調整與優化專案的資源分配，從而逐步提高項目的淨現值。其他演化式演算法中的相應技術，如交叉遺傳、反向變異、精英策略，亦加以採用以加速演算法的搜索進程。該演算法亦採用反向調度技術進一步調整進度計畫，以提高專案淨現值。計算實驗的結果顯示，本文所提出的蟻群演算法可以較顯著地改進資源受限專案的淨現值。

An ant colony algorithm is proposed to improve the net present values of resource-constrained projects since the net present value is a critical criterion for a project with a long time span and considerable cash flows. The algorithm adaptively adjusts the allocation of scarce resources according to the pheromone generated by artificial ants in the previous iterations so as to maximize the project's net present value. The crossover operation, inverse mutation and elitist strategy are applied to accelerate the searching for better project schedules, and the backward scheduling technique is adopted to improve the net present value further. The experimental test results show that the proposed algorithm significantly improves the net present values of resource-constrained projects.

1. Abbasi, G. Y.,Y. A. Arabiat(2001).A heuristic to maximize the net present value for resource-constrained project scheduling problems.Project Management Journal,32,17-24.
2. Baroum, S. M.,J. H. Patterson(1996).The development of cash flow weight procedures for maximizing the net present value of a project.Journal of Operations Management,14,209-227.
3. Brucker, P.,A. Drexl,R. Mohring(1999).Resource-constrained project scheduling: Notation, classification, models, and methods.European Journal of Operational Research,112,3-41.
4. Herroelen, W.,B. de Reyck,E. Demeulemeester(1998).Resource-constrained project scheduling: A survey on recent developments.Computers & Operations Research,25,279-302.
5. Herroelen, W.,P. van Dommelen,E. Demeulemeester(1997).Project network models with discounted cash flows: A guided tour through recent developments.European Journal of Operational Research,100,97-121.
6. Kurtulus, I.,E. W. Davis(1982).Multi-project scheduling: Categorization of heuristic rules performance.Management Science,28,161-172.
7. Li, K. Y.,R. J. Willis(1992).An iterative scheduling technique for resource-constrained project scheduling.European Journal of Operational Research,56,370-379.
8. Merkle, D.,M. Middendorf(2000).An ant algorithm with a new pheromone evaluation rule for total tardiness problems.Lecture Notes in Computer Science.
9. Merkle, D.,M. Middendorf,H. Schmeck(2000).Ant colony optimization for resource-constrained project scheduling.Proceedings of the Genetic and Evolutionary Computation Conference.
10. Patterson, J. H.(1984).A comparison of exact approaches for solving the multiple constrained resource, project scheduling problem.Management Science,30,854-867.
11. Pinder, J.P.,A. S. Marucheck(1996).Using discounted cash flow heuristics to improve project net present value.Journal of Operations Management,14,229-240.
12. Shou, Y. Y.(2005).A random sampling technique for improving the net present value of resource-constrained projects.Proceedings of 2005 Chinese Control & Decision Conference.
13. Ulusoy, G.,L. Ozdamar(1995).A heuristic scheduling algorithm for improving the duration and net present value of a project.International Journal of Operations and Production Management,15,89-98.
14. Yang, K. K.,C. C. Sum(1997).An evaluation of due date, resource allocation, project release, and activity scheduling rules in a multi-project environment.European Journal of Operational Research,103,139-154.
15. Yang, K. K.,L. C. Tay,C. C. Sum(1995).A comparison of stochastic scheduling rules for maximizing project net present value.European Journal of Operational Research,85,327-339.