引用本文

陆志强, 刘欣仪. 考虑资源转移时间的资源受限项目调度问题的算法. 自动化学报, 2018, 44(6): 1028-1036. doi: 10.16383/j.aas.2017.c160834

LU Zhi-Qiang, LIU Xin-Yi. Algorithm for Resource-constrained Project Scheduling Problem With Resource Transfer Time. ACTA AUTOMATICA SINICA, 2018, 44(6): 1028-1036. doi: 10.16383/j.aas.2017.c160834

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160834

关键词

项目调度，资源受限，资源转移时间，内嵌分支定界的遗传算法 

摘要

现有项目调度问题的研究一般假设资源在任务间转移不需要时间，但这一假设与很多实际情况不相符，本文在资源受限项目调度问题（Resource-constrained project scheduling problem，RCPSP）中引入资源转移时间，以最小化项目工期为目标，建立了考虑资源转移时间的资源受限项目调度问题的数学模型.为改善遗传算法在局部搜索能力方面的不足，提出将分支定界法与遗传算法相结合，构造了一种内嵌分支定界寻优搜索的遗传算法，在保证算法全局搜索能力的前提下提升局部精确搜索能力.同时，对于遗传算法，为了适应算法结构提出了一种基于任务绝对顺序的编码策略.数据实验表明，对于小规模问题可获得近似精确解，对于大规模问题相较现有文献所提算法，在算法求解精度上可提升10%.

文章导读

经典资源受限项目调度问题(Resource-constrained project scheduling problem, RCPSP)假设任务在其紧前任务结束后即可开始, 但是这一假设与很多实际情形不符.在许多工程项目尤其是大型项目(例如飞机装配线生产)中, 因为各工位所处的位置不同, 当一些稀缺资源(例如高级技工或关键设备)在不同工位间转移时需要消耗一定的转移时间.本文以飞机装配线生产为研究背景, 将其抽象为资源受限项目调度问题, 同时考虑到飞机装配线生产问题中稀缺资源在不同的工位间转移需要消耗时间, 为了能够使理论模型处理这一实际情况, 本文研究带资源转移时间的资源受限项目调度问题, 分析转移时间对项目调度决策造成的影响, 并研究该类问题的建模与有效求解算法.

对于资源受限项目调度问题, 目前的求解算法主要有精确算法、构造型启发式算法和元启发式算法.精确算法主要以分支定界法为主, 例如Brucker等[1]和Dorndorf等[2].虽然精确算法能够求得问题的精确解, 但是计算时间较长, 无法适用于大规模问题, 而构造型启发式算法和元启发式算法能在可接受时间内求得问题的相对较优解.构造型启发式算法以基于规则的启发式算法为主, 通常根据不同的任务优先规则确定任务优先级, 使用串行或并行调度生成机制获得调度结果, 例如Klein[3]和Buddhakulsomsiri等[4].元启发式算法方面, 多使用遗传算法和模拟退火算法等搜索算法, 采用任务优先级编码或任务列表编码, 通过搜索方法获取较优编码, 并使用串行或并行调度生成机制解码获取较优调度结果, 例如Valls等[5], Peteghem等[6], Cho[7]等.对于带资源转移时间的资源受限项目调度问题, 目前有极少文献进行了研究, Krüger等[8]最先提出了带资源转移时间的资源受限项目调度问题, 假设资源在任务间及多项目间转移都需要资源转移时间, 问题的求解中采用了基于规则的启发式方法. Krüger等[9]对资源传递过程中的资源进行了定义和分类, 分为被传递的资源和协助资源传递的辅助资源, 建立了带资源转移时间的资源受限项目调度问题的扩展模型.宗砚等[10]建立了一种考虑资源传递时间并以多项目总工期及各个项目工期的加权和最小为目标的多项目调度模型, 并提出一种基于三级启发式规则解码的改进遗传算法求解.在带资源转移时间的项目调度问题中, 资源转移时间与任务顺序两者互相耦合, 转移时间会随任务顺序的不同发生变化, 而这种变化又会影响任务执行顺序的决策, 因此在决策任务顺序的同时应进一步考虑资源转移时间造成的影响.虽然上述文献对带资源转移时间的问题进行了一些研究, 但是在求解问题时, 都只提出了简单的启发式思路, 未能对资源转移时间与作业顺序调度决策的相互影响做进一步分析, 仍然存在可以改进的空间.

综上所述, 目前的求解算法中, 精确算法无法求解大规模问题, 构造型启发式算法虽然求解效率快, 但是单一的规则无法适用于不同的问题结构, 相对精确算法和元启发式算法而言, 这一类算法往往无法求得较优的任务顺序.而元启发式算法虽然通过搜索方法可以获得较优编码(任务顺序), 但是在解码时多使用启发式方法进行解码, 例如经典的串、并行调度生成机制, 在求解的精度上仍有欠缺.针对以上问题, 本文提出一种内嵌分支定界的遗传算法, 将遗传算法与分支定界法相结合, 使用遗传算法框架保证算法的广度搜索能力并避免枚举所有分支, 同时使用基于深度优先的分支定界法进行深度搜索, 有效提高解的质量.同时, 本文分析了资源转移时间对于问题解的影响, 并由此提出了相应的支配规则并应用于分支定界算法, 从而提升分支搜索的效率.

图 1  算法流程图

图 2  编码的生成方式

图 3  带资源转移时间的资源受限项目调度问题实例

本文提出一种内嵌分支定界的遗传算法求解带有资源转移时间的资源受限项目调度问题, 算法使用遗传算法保证全局搜索能力, 同时使用基于深度优先的分支定界算法优化局部邻域搜索能力, 基于对问题结构的研究提出并证明了相应的支配规则, 并提出了问题的动态下界, 提升了分支定界算法的搜索效率.通过数据实验验证了本文所提内嵌分支定界的遗传算法的有效性.在求解小规模问题时, 算法所得解与最优解间的差值均在1%以下; 在求解大规模问题时, 相较现有文献的启发式算法, 内嵌分支定界的遗传算法可以提高解的精度近10%.

作者简介

刘欣仪

同济大学硕士研究生.2015年获得同济大学学士学位.主要研究方向为项目调度.E-mail:liuxinyi@tongji.edu.cn

陆志强  

同济大学教授.2003年获得法国南特大学博士学位.主要研究方向为物流与供应链管理.本文通信作者.E-mail:zhiqianglu@tongji.edu.cn