基于变邻域搜索和布图规划的资源投资项目调度方法研究

摘要

在科技飞速发展的今天，项目调度问题越来越成为人们关注的焦点。资源投资项目调度问题(Resource Investment Project Scheduling Problems,RIPSPs)是项目调度问题的一个重要拓展，它解除了资源约束项目调度问题(Resource-Constrained Project Scheduling Problems,RCPSPs)中给定各种资源总量的限制，即问题变为给定一个项目，项目中包含多个活动，活动之间有优先约束关系，并且每个活动的执行都需要一定的时间以及若干种资源。我们的任务是合理的安排活动之间的优先约束关系，使得项目的完工时间最短，同时要满足项目执行的过程中需要的每种最大资源容量（称之为可用资源容量）最小。本文针对单模式 RIPSPs，用不同的方法进行了研究，包括变邻域搜索(Variable Neighborhood Search,VNS)，基于多智能体进化算法(Multi-agent Evolutionary Algorithm,MAEA)的VNS以及布图规划中的基于移动模块序列(Moving Block Sequence,MBS)的方法。主要研究内容总结如下：
　　1.在基于 VNS的方法中，采用抖动操作及邻域搜索算子，首先每个解由一个满足优先约束关系的活动列表和一个资源容量列表组成，然后从问题的一个可行解开始搜索，通过邻域搜索算子找到局部最优解，然后利用抖动操作跳出局部最优解并继续进行搜索，就这样不停的扩大搜索空间，直到找到最优解或者达到停止条件为止。采用桥构建数据集以及产生实例集J10、J14和J20验证算法性能，实验结果表明VNS比较适合解决小规模问题集。
　　2.在第一项基于VNS工作的基础上，加入MAEA，采用选择、交叉、变异、竞争等算子优化算法性能，对于当前代中最好的智能体，以1/2的概率应用自学习算子或基于VNS的局部搜索算子进一步搜索解的空间，实验表明所提出的算法性能良好。
　　3.提出将布图规划中MBS的表示方法和MAEA相结合求解RIPSPs。首先将项目中的每个活动看作MBS中的一个硬矩形模块，模块的宽度代表活动的执行时间，高表示活动的最大资源需求量。每个模块都有四个初始位置，并且每个初始位置都对应着一种移动方式。所有模块的移动范围均限定在第一象限，并且移动的过程中不仅要保证模块之间的优先约束关系，还要保证模块之间不能重叠。算法采用基于 MBS的两点交叉、具有方向性的变异、竞争以及自学习等算子去搜索最优解。实验结果表明算法性能良好，能够比较好的解决RIPSPs。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1资源投资项目调度问题描述

1.2资源投资项目调度问题的数学模型

1.3资源投资项目调度问题的求解方法

1.4变邻域搜索算法

1.5布图规划方法

1.6基于多智能体的进化算法

1.7本文工作及论文章节安排

第二章 变邻域搜索解决资源投资项目调度问题

2.1引言

2.2变邻域搜索算法

2.3实验

2.4小结

第三章 变邻域结合多智能体进化算法解决资源投资项目调度问题

3.1引言

3.2基于资源投资项目调度问题的智能体

3.3多智能体的产生

3.4智能体的算子

3.5算法流程

3.6实验

3.7小结

第四章 基于移动模块序列的布图规划解决资源投资项目调度问题

4.1引言

4.2资源投资项目调度问题中移动模块序列的表示

4.3将一个移动模块序列转换为一个调度

4.4算子

4.5算法流程

4.6实验

4.7小结

第五章 总结与展望

5.1总结

5.2展望

参考文献

致谢

作者简介