一个资源约束项目调度模型及其启发式算法研究

摘要

针对某企业的生产需求，实际生产调度中存在位置限制及一些特殊的工序间关系约束，最小化最大完工时间是其最终的优化目标。由于该类问题与实际生产的效率与投入成本密切相关，因此其具有重要的研究价值。而目前的研究中并不存在解决此类问题的相关模型，因此本文通过对经典资源约束项目调度问题（Resource-constrained Project Scheduling Problem，RCPSP）的学习与研究，加入了工位约束及工序与资源间的约束，建立了一种特殊的资源约束项目调度问题模型。同时结合实际应用需求，提出了一个基于优先规则的构造型启发式算法。
　　本文首先结合经典的资源约束项目调度问题详细分析了实际项目中存在的约束，重点阐述了在加入工位后，模型中的资源、工件与工序所受到的约束影响。接着结合已分析问题中的资源约束与工序约束，构建了一种特殊的资源约束项目调度问题，同时确定其问题目标为最小化最大完工时间，并提出了通用的问题模型。最后为了求解提出的新型问题模型，本文基于串行调度生成方案提出了一个求解目标为最小化最大完工时间的构造型启发式算法。在该算法中，主要使用了三种启发式规则，分别是:为工件选择最早可用且可加工工序数最多的工位、为工序配置最早可用且加工能力最强的可更新资源、在调度阶段中优先调度完工时间最早的工序。同时针对调度过程中可能产生的死锁问题，本文提出了相应的两种解决方法。
　　结合实际生产数据，本文设计了实验方案，并对该实际算例进行了详细描述，将其作为本文提出的算法的输入数据，从而对该算法进行实验。实验结果表明该算法能够快速地构造问题的解，节省了大量的人力资源，并且可得到更优的调度方案。

目录

声明

致谢

摘要

1 引言

1．1 研究背景与意义

1．2 国内外研究现状

1．3 论文主要内容

1．4 论文组织结构

1．5 本章小结

2 经典资源约束项目调度问题及求解算法

2．1 约束描述

2．1．1 逻辑约束

2．1．2 资源约束

2．2 问题目标

2．3 经典资源约束项目调度问题模型描述

2．4 扩展的问题模型

2．5 算法研究现状

2．5．1 精确算法

2．5．2 启发式算法

2．6 本章小结

3 一种特殊的资源约束项目调度问题

3．1 环境概念描述及分析

3．1．1 工位描述

3．1．2 资源描述

3．1．3 工件描述

3．1．4 工序描述

3．2 问题模型描述

3．2．1 资源约束

3．2．2 工序约束

3．2．3 问题目标

3．3 本章小结

4 调度算法设计

4．1 算法涉及概念

4．2 算法主要思想

4．3 优先规则

4．4 死锁问题及解锁规则

4．5 SSGS算法设计

4．5．1 算法框架设计

4．5．2 SSGS算法总调度流程设计

4．5．3 选择候选调度工件集设计

4．5．4 工件能否在当前工位调度设计

4．5．5 工序能否在当前工位获得所需资源设计

4．5．6 选择工位设计

4．5．7 调度工序设计

4．5．8 更新调度工序集设计

4．6 本章小结

5 实验及分析

5．1 实验方案设计

5．2 算例描述

5．3 实验结果及分析

5．4 本章小结

6 总结与展望

6．1 论文总结

6．2 不足与展望

参考文献

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

学位论文数据集