Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows： A Monte Carlo Ant Colony System Approach

• Published in: Journal of computer science and technology 2012-09, Vol.27 (5), p.950-965
• Main Author: 陈伟能 张军
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Artificial Intelligence; Computer Science; Computer simulation; Computing costs; Costs; CS算法; Data Structures and Information Theory; Expected values; Heuristic; Information Systems Applications (incl.Internet); Mathematical models; Monte Carlo methods; Monte Carlo simulation; Net present value; Optimization; Pheromones; Project management; Random variables; Regular Paper; Resource scheduling; Schedules; Scheduling; Software Engineering; Studies; Theory of Computation; Traveling salesman problem; Uncertainty; 多模式; 现金流量; 蒙地卡罗; 蚁群系统; 调度优化; 随机变量; 项目调度
• ISSN: 1000-9000; 1860-4749
• DOI: 10.1007/s11390-012-1276-2

Project scheduling under uncertainty is a challenging field of research that has attracted increasing attention. While most existing studies only consider the single-mode project scheduling problem under uncertainty, this paper aims to deal with a more realistic model called the stochastic multi-mode resource constrained project scheduling problem with discounted cash flows （S-MRCPSPDCF）. In the model, activity durations and costs are given by random variables. The objective is to find an optimal baseline schedule so that the expected net present value （NPV） of cash flows is maximized. To solve the problem, an ant colony system （ACS） based approach is designed. The algorithm dispatches a group of ants to build baseline schedules iteratively using pheromones and an expected discounted cost （EDC） heuristic. Since it is impossible to evaluate the expected NPV directly due to the presence of random variables, the algorithm adopts the Monte Carlo （MC） simulation technique. As the ACS algorithm only uses the best-so-far solution to update pheromone values, it is found that a rough simulation with a small number of random scenarios is enough for evaluation. Thus the computational cost is reduced. Experimental results on 33 instances demonstrate the effectiveness of the proposed model and the ACS approach.