论文部分内容阅读
资源约束项目调度问题(Resource-Constrained Project Scheduling Problem, RCPSP)是一类应用十分广泛的组合优化问题,主要研究项目在满足资源约束和紧前关系约束的前提下,通过合理安排任务的开始和结束时间,来达到一定的优化目标。该类问题的模型一般是基于单目标调度建立起来的,因此一般只能用来解决单目标问题。然而随着社会的不断发展以及企业项目进程的不断深入,一个项目往往要面对多个目标,从而需要通过建立多目标调度的问题模型来解决该类问题。不过,由于多目标问题本身的复杂性,目前针对多目标资源约束项目调度问题的研究非常少。基于此,本文在对国内外蚁群优化算法的研究动态和理论现状作了较为详细的介绍之后,对双种群蚁群算法的优越性进行了总结,并提出了基于工期和成本的双种群蚁群算法,尝试通过双种群蚁群算法的运用,解决项目目标为总工期和总成本最小化的多模式资源约束项目调度问题。主要工作为:考虑将蚁群分成两个种群,分别对应不同的目标函数,通过共享各自种群的信息素使搜索结果的反馈得以交流,通过设计相应的转换规则、信息素定义、启发式定义以及精英策略完成对双种群蚁群算法模型的构建。为了验证该模型在解决多目标问题上的可行性,本文最后通过一个项目实例的应用,将由双种群蚁群算法求得的结果与由单种群蚁群算法求得的结果进行比较。对于双种群蚁群算法和单种群蚁群算法之间的评价通过单一目标的评价和综合目标的评价两方面进行:从单一目标值着手,将运用双种群蚁群算法求得的解与运用单种群蚁群算法求得的解分别和目标值进行比较;从综合目标值着手,将工期成本两个目标归一化为一个目标,计算其与综合目标值的偏差。最后基于以上的比较分析,来说明双种群蚁群算法在求解工期成本优化问题上的可行性与优越性。在基本完成了预期目标的同时,本文也发现了研究过程中存在的一些问题,如何克服这些问题并将双种群蚁群算法发展成为在科学研究和工程实践领域更具优势的元启发式算法是今后值得思考的一个方向。