一个带计划型故障的资源受限多项目调度问题的智能优化算法研究

发布时间：2020-04-17 10:49

【摘要】：带有资源故障的资源受限多项目调度问题是经典资源受限多项目调度问题(RCMPSP)的扩展问题,并且在实践中普遍存在。由于这类问题通常比较复杂而且模型多样,所以很难建立统一的问题模型去求解,目前相关研究较少。本文以某一实际生产场景为背景,建立问题模型并研究求解算法,主要研究内容如下:首先,建立了一个带有计划型故障的资源受限多项目调度问题模型(RCMPSP-PRU),问题目标是最小化项目的最大完工时间。RCMPSP-PRU在经典RCMPSP的基础上,增加了一些新概念,如工位、可移动资源、不可移动资源、计划型故障等,并综合考虑了多种复杂约束关系。其次,对串行进度生成机制做了改进,并根据问题特征设计了调度优先级规则,进而提出了基于优先级规则的改进串行进度生成算法ISSPR。实验结果表明,ISSPR可以快速给出合理可行的调度计划。然后,针对ISSPR算法中影响调度计划的工件换位顺序和计划型故障两个重要因素,分别提出了两个单因素优化算法:工件换位顺序的遗传算法GAJTO和计划型故障的禁忌搜索算法TSPRU。实验结果表明,算法GAJTO和TSPRU对ISSPR解的质量均有明显的优化效果。但算法GAJTO存在收敛速度慢,耗时长的问题。最后,为解决算法GAJTO耗时长的问题,提出了针对工件换位顺序的遗传-粒子群混合优化算法JTO-PSOGA。实验结果表明,JTO-PSOGA可以在保证GAJTO优化效果的同时明显提升求解效率。然后,在单因素优化算法JTO-PSOGA和TSPRU的基础上,提出了基于遗传-粒子群和禁忌搜索的优化算法JP-PSOGATS。在JP-PSOGATS中,遗传-粒子群混合算法用来优化工件换位顺序,禁忌搜索算法用来解决计划型故障。实验结果表明,JP-PSOGATS可取得较本文其他优化算法更好的优化效果,但同时需要更多的求解时间。结合本文的问题特征,并权衡求解质量与求解效率的关系后,认为较本文其他优化算法而言,JP-PSOGATS的优化效果最理想。
【图文】：

示意图,工序,子项目,资源库

开始－结束型（ｓｔａｒｔ－ｆｉｎｉｓｈ）逦ＳＦ逦工序Ｂ在工序Ａ开始之前不可以结束逡逑图１－２工序ＡＯＮ网络示意图逡逑Ｆｉｇｕｒｅ邋１－２邋Ｔｈｅ邋ＡＯＮ邋ｏｆ邋ｔｈｅ邋ｏｐｅｒａｔｉｏｎｓ：邋ａｎ邋ｅｘａｍｐｌｅ逡逑１．１．２经典ＲＣＭＰＳＰ模型简介逡逑ＲＣＭＰＳＰ是指在一个总项目中包含多个并行的子项目和一个资源库。在每个逡逑子项目中，存在多个任务需要完成。完成这些任务需要一定的资源和时间，，各项逡逑目之间除共享同一个资源库外，其他均独立。资源之间以及各任务之间均存在约逡逑束关系。ＲＣＭＰＳＰ的最终目的就是在满足资源及其他一系列约束条件的情况下，逡逑４逡逑

示意图,工序,示意图,子项目

Ｂ—ｙ逡逑图１－１工序之间关系不意图逡逑Ｆｉｇｕｒｅ邋１－１邋Ｔｈｅ邋ｒｅｌａｔｉｏｎｓｈｉｐ邋ｂｅｔｗｅｅｎ邋ｏｐｅｒａｔｉｏｎｓ逡逑表１－１工序之间约束关系类型及含义逡逑Ｔａｂｅｌ邋１－１邋Ｔｈｅ邋ｒｅｌａｔｉｏｎｓｈｉｐ邋ｂｅｔｗｅｅｎ邋ｏｐｅｒａｔｉｏｎｓ邋ａｎｄ邋ｔｈｅ邋ｃｏｒｒｅｓｐｏｎｄｉｎｇ邋ｍｅａｎｉｎｇ逡逑约束关系类型逦逦逡逑结束－开始型（ｆｉｎｉｓｈ＿ｓｔａｒｔ）逦ＦＳ逦工序Ｂ必须在工序Ａ结束后才可开始逡逑结束－结束型（ｆｉｎｉｓｈ－ｆｉｎｉｓｈ）逦ＦＦ逦工序Ｂ必须在工序Ａ结束后才可结束逡逑开始＿开始型（ｓｔａｒｔ－ｓｔａｒｔ）逦ＳＳ逦工序Ａ在开始之前工序Ｂ不可以开始逡逑开始－结束型（ｓｔａｒｔ－ｆｉｎｉｓｈ）逦ＳＦ逦工序Ｂ在工序Ａ开始之前不可以结束逡逑图１－２工序ＡＯＮ网络示意图逡逑Ｆｉｇｕｒｅ邋１－２邋Ｔｈｅ邋ＡＯＮ邋ｏｆ邋ｔｈｅ邋ｏｐｅｒａｔｉｏｎｓ：邋ａｎ邋ｅｘａｍｐｌｅ逡逑１．１．２经典ＲＣＭＰＳＰ模型简介逡逑ＲＣＭＰＳＰ是指在一个总项目中包含多个并行的子项目和一个资源库。在每个逡逑子项目中，存在多个任务需要完成。完成这些任务需要一定的资源和时间，各项逡逑目之间除共享同一个资源库外，其他均独立。资源之间以及各任务之间均存在约逡逑束关系。ＲＣＭＰＳＰ的最终目的就是在满足资源及其他一系列约束条件的情况下，逡逑４逡逑
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【参考文献】