基于工位的资源受限项目调度问题的模型研究与调度算法实现

摘要

资源受限项目调度问题(Resource-constrained Project Scheduling Problem，RCPSP)包含一组在调度过程中必须满足优先关系和资源约束的任务，常见调度目标是最小化最大完工时间(Makespan)。在生产系统或服务组织中，存在这么一类问题，相对于RCPSP，额外拥有一定数量不同类型的工位，任务需要在特定的工位上执行，每个资源只能服务有限的工位，工件或可移动的资源在工位之间移动需要一定的时间，调度目标也是最小化最大完工时间。在以前RCPSP研究中，缺少对工件和资源位置的考虑，因此上述问题不能直接使用RCPSP模型进行求解。本文将对基于工位约束的资源受限项目调度问题(Site-based and Resource-constrainedProject Scheduling Problem，SRCPSP)做以下详细描述与分析。
　　首先，本文在介绍RCPSP及其各种扩展约束后，分析了工位的基本约束，并对工位与资源、工位与工件和工位与任务之间的约束进行了详细的分析与公式化描述。结合任务优先关系与工位的约束，证明了任务的同工位特性，定义了同工位任务。基于同工位任务提出了任务子网(Sub-net，SN)和联合子网(CombinedSub-nets，CSN)的概念，并设计了SN和CSN的求解流程，将工位约束与RCPSP模型结合，给出了SRCPSP的模型。
　　其次，为了在可接受时间内获得SRCPSP的可行解，本文提出两个基于优先规则的启发式调度算法，分别是基于任务子网的搜索算法(Sub-net Based Searchalgorithm，SNBS)和基于联合子网的搜索算法(Combined Sub-nets Based Searchalgorithm，CSNBS)。此外，为更好的解释上述算法，文中给出了SNBS算法和CSNBS算法的流程图。
　　最后，本文使用项目调度仿真平台获得了可用于验证算法正确新的两组测试实例。实验结果表明SNBS在时间效率上优于CSNBS，但CSNBS较SNBS获得了更小的项目完工时间。并且基于测试实例，验证两个算法都优于人工调度算法。

目录

声明

致谢

摘要

1 引言

1．1 研究背景与意义

1．2 国内外研究现状

1．3 论文主要内容

1．4 论文基本结构

1．5 本章小结

2 资源受限项目调度问题描述

2．1 扩展约束介绍

2．1．1 任务约束

2．1．2 资源约束

2．1．3 优先关系约束

2．1．4 广义优先关系

2．2 问题模型分析

2．2．3 问题求解目标

2．2．4 问题常见模型

2．3 算法研究现状

2．3．1 精确算法

2．3．2 启发式算法

2．3．3 超启发式算法

2．4 本章小结

3 基于工位的项目调度问题

3．1 工位及其约束介绍

3．2 工件约束分析

3．3 资源约束分析

3．4 任务约束分析

3．4．1 同工位任务

3．4．2 任务子网

3．4．3 联合子网

3．4 问题建模与分析

3．5 本章总结

4 启发式调度算法

4．1 算法主要思想

4．2 基于规则的本地搜索算法

4．2．1 实验算法框架设计

4．2．2 SNBS算法设计

4．2．3 CSNBS算法设计

4．2．4 工位调度设计

4．2．5 资源调度设计

4．3 本章总结

5 实验及分析

5．1 实验数据生成

5．2 实验方案设计

5．3 实验结果分析

5．4 本章总结

6 总结与展望

参考文献

附录A 实验数据数据格式

作者简历

学位论文数据集