运用蚁群算法优化资源受限项目调度问题的研究

摘要

项目调度问题(Project Scheduling Problem，PSP)是指对一个工程项目中的多项任务进行调度，在满足项目本身的各项约束条件的前提下确定其中各项任务的开始执行时间，尽可能达到项目本身的各种目标要求。资源受限型PSP问题(Resource-Constrained Project Scheduling Problem，RCPSP)是一个经典的lNP-难问题，它在现实工作和理论上都有着重要意义。 传统的RCPSP优化问题主要是以最短工期、最小费用为优化目标。近年来，学者们在RCPSP中引入资金管理目标，拓广了该问题的现实意义和实用性能，并逐渐成为这一领域的研究热点。同时，现金管理目标的引入使得问题求解的计算复杂性进一步提高，对问题的优化算法提出了更高的要求。针对此类问题，当前提出的启发式算法很少，而一类在传统RCPSP中已经展现出优异性能的元启发式算法——蚁群算法，还没有应用在这类问题中。 本研究的重点是利用蚁群算法来实现带资金管理目标的RCPSP的求解。基于一个称为多模式资源约束型折现流时间一费用权衡项目调度问题(MICTCTPDF)<'[1]>的模型，以最大化现金流的净现值(NPV)为目标，本文通过设计相应的转换规则、信息素定义、启发式定义、对蚁群算法作出相应的修改，提出一种蚁群系统(Ant Colony System)算法来求解MRCTCTPDF。通过实例进行测试，实验结果验证了这个算法的有效性。

目录

文摘

英文文摘

第1章 引言

第2章 项目调度问题综述

第3章 蚁群算法概述

第4章 用蚁群算法求解离散问题的研究

第5章 运用蚁群算法优化项目调度中的现金流问题

第6章 结论

参考文献

致谢

原创性声明