We use cookies to improve your experience with our site.
陈伟能, 张军. 基于蒙特卡罗蚁群系统的不确定性多模式项目调度现金流优化[J]. 计算机科学技术学报, 2012, 27(5): 950-965. DOI: 10.1007/s11390-012-1276-2
引用本文: 陈伟能, 张军. 基于蒙特卡罗蚁群系统的不确定性多模式项目调度现金流优化[J]. 计算机科学技术学报, 2012, 27(5): 950-965. DOI: 10.1007/s11390-012-1276-2
Wei-Neng Chen, Jun Zhang. Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach[J]. Journal of Computer Science and Technology, 2012, 27(5): 950-965. DOI: 10.1007/s11390-012-1276-2
Citation: Wei-Neng Chen, Jun Zhang. Scheduling Multi-Mode Projects under Uncertainty to Optimize Cash Flows: A Monte Carlo Ant Colony System Approach[J]. Journal of Computer Science and Technology, 2012, 27(5): 950-965. DOI: 10.1007/s11390-012-1276-2

基于蒙特卡罗蚁群系统的不确定性多模式项目调度现金流优化

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

  • 摘要: 带不确定性的项目调度是一个新兴的具挑战性的研究领域。当前带不确定性的项目调度研究主要基于单模式的项目。为使调度模型及算法更加贴近实际, 考虑了一类更复杂的不确定性项目调度问题:带折现流的随机多模式资源受限项目调度问题(S-MRCPSPDCF)。该问题模型的活动时间和费用以随机变量给出, 并以最大化项目现金流净现值(NPV)的期望值为优化目标。针对该问题, 提出了基于蚁群系统(ACS)的调度算法, 通过人工蚂蚁反复地根据信息素和基于费用折现期望值的启发信息来构造解而实现对待解问题的不断寻优。由于问题模型包含随机变量, 解的质量不能通过确定性的表达式直接求解, 而只能通过蒙特卡罗仿真方法进行评估。蒙特卡罗仿真需要大量的计算开销。然而, 由于蚁群系统算法的信息素更新操作只依赖于算法发现的至今最优解, 因此, 通过对非最优解采用粗糙的模特卡罗仿真策略, 可以以较少的仿真采样数来维持蚁群系统算法优化过程的正常工作, 从而有效地降低了算法的计算代价。在33个实例上进行的数值实验结果证明了提出算法的有效性。

     

    Abstract: 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.

     

/

返回文章
返回