一个特殊资源约束项目调度问题模型及其优化算法研究

摘要

项目调度问题在企业生产中有着很重要的作用，与生产效率、成本密切相关。由于企业生产过程的多样性，经典资源约束项目调度问题(RCPSP)在实际生产中并不适用，所以，本文基于某企业的实际需求，在RCPSP基础上加入了工位、工件等新的概念，增加了工位对可更新资源、工件加工的约束，设定最小化总流程时间和最小化总偏差时间为求解目标，提出了一个新的项目调度问题模型—特殊资源约束项目调度问题(SRCPSP)，用以解决实际调度问题。
　　由于RCPSP是NP-hard问题，而SRCPSP约束更为复杂，所以，只能使用启发式算法进行求解。本文首先使用基于串行进度生成机制和优先规则的启发式算法对SRCPSP进行求解，提出了三大类规则分别用于选择工位、选择资源和选择工序，实验表明该算法可以快速生成一个初始可行解。然后，在此基础上，对初始解进行优化算法研究。首先，本文实验了使用迭代局部搜索的方法，研究了使用迭代局部搜索时解的表示方式、邻域结构、扰动策略等，然而研究表明，由于工件在工位间移动的巨大时间代价，迭代局部搜索并不适用于带工位约束的项目调度问题。之后，考虑到工序的调度主要是合适的工位和资源，所以本文实验了为工序随机选择工位和资源，结果表明，随机选择工位可以产生更好的结果。根据此结果，本文将蚁群优化算法—最大最小蚂蚁系统(MMAS)—应用到工位选择上，并用实验确定了蚁群算法中各项参数。实验表明，使用最大最小蚂蚁系统优化工位选择过程的方法是切实有效的，并且在生成相同数量解的情况下，相较于随机选择是稳定较优的。
　　因此，对于本文提出的SRCPSP模型，设计的基于MMAS的优化算法具有很好的求解效果，将MMAS应用到工位选择上是合理有效的。

目录

声明

致谢

摘要

1 引言

1．1 研究背景及意义

1．1．1 基本概念及约束

1．1．2 RCPSP模型

1．1．3 求解算法

1．1．4 RCPSP局限性及本文研究意义

1．2 国内外研究现状

1．2．1 RCPSP模型扩展研究现状

1．2．2 算法研究现状

1．3 论文主要内容和组织结构

1．4 本章小结

2 特殊资源约束项目调度问题模型

2．1 环境数据

2．1．1 工件

2．1．2 工位

2．1．3 资源

2．1．4 工序

2．2 约束关系

2．2．1 资源约束

2．2．2 工序约束

2．3 问题目标

2．4 模型举例

2．5 本章小结

3 基于优先规则的SSGS启发式算法

3．1 基本概念及定义

3．2 算法总体流程

3．3 优先规则

3．3．1 工位选择规则

3．3．2 资源选择规则

3．3．3 工序选择规则

3．3．4 解锁规则

3．4 输入及输出数据格式

3．4．1 输入数据

3．4．2 输出数据

3．5 本章小结

4 基于迭代局部搜索的优化算法

4．1 迭代局部搜索算法

4．2 SRCPSP问题的迭代局部搜索优化算法设计

4．2．1 解的表示

4．2．2 邻域结构

4．2．3 扰动策略

4．2．4 算法总流程设计

4．3 实验与结果分析

4．4 本章小结

5 基于蚁群算法的优化算法

5．1 随机抽样算法

5．1．1 工位随机选择算法

5．1．2 资源随机选择算法

5．1．3 实验验证及分析

5．2 蚁群算法

5．2．1 蚁群优化算法

5．2．2 基于MMAS的优化算法设计与实现

5．2．3 基于MMAS的优化算法参数选择

5．3 实验结果与分析

5．3．1 测试用例描述

5．3．2 性能和可行性测试

5．3．3 MMAS优化算法与随机算法对比

5．4 本章小结

6 总结与展望

6．1 本文总结

6．2 展望及今后的工作

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集