IEEEJAS的个人博客分享 http://blog.sciencenet.cn/u/IEEEJAS

博文

资源约束项目的改进差分进化参数控制及双向调度算法

已有 1801 次阅读 2020-5-11 18:14 |系统分类:博客资讯

资源约束项目调度问题(Resource-constrained project scheduling problem, RCPSP)是指在满足项目资源约束及项目任务开始时间顺序约束的前提下,以项目的最小工期为目标,安排最优的任务开始时间。目前求解RCPSP的算法主要分三类:适用于小规模、复杂度低的精确算法;基于调度优先规则的启发式算法;具有较好鲁棒性的元启发式算法,如遗传算法、粒子群算法、蚁群算法、模拟退火、禁忌搜索、差分进化等。RCPSP属于组合优化难题,如何获得较低的平均偏差率及较好的求解性能,一直倍受国内外学者关注。


针对资源约束项目调度组合优化难题,本文提出一种改进的动态差分进化参数控制及双向调度算法(Adaptive dynamic differential evolution based bidirectional scheduling, ADDE-BS)。通过参数时变衰减与个体优劣评价,自适应控制个体进化参数,提高算法收敛性能、勘探与开发最优解的能力;基于动态差分进化(Dynamic differential evolution, DDE),提出一种双向调度算法,使用满足任务时序约束的优先数编码、交替正向反向调度,结合标准化编码调整与精英保留的种群随机重建策略,建立了一种高效稳健的双向编码调整机制。通过著名的项目调度问题库(Project scheduling problem library, PSPLIB)中实例集测试,并与其他文献算法比较最优解平均偏差率,验证了所提算法的有效性与优越性。


如式(1)~(3)所示,参数自适应控制方法中,Pi(t)综合考虑参数时变衰减α(t)与个体目标值优劣评价βi,自适应控制个体缩放因子F与交叉概率CR,使种群获得稳健的全局搜索与局部开发能力,减少了选择参数时的经验依赖性以及搜索盲目性,有利于改进算法收敛性能。


1.jpg


如图1所示,个体用随机数数组编码表示,任务编号对应于数组索引号。初始化种群时,如果直接按照编码升序来重排任务编号,那么生成的任务调度序列5-3-6-4-2-1将违背时序约束。因此,在个体初始随机编码的基础上,根据时序约束进行编码调整,形成满足时序约束的个体拓扑编码及任务调度序列。双向调度过程中,正向调度指先安排前序任务,再安排后继任务的调度方式。从虚任务1开始,根据任务调度顺序列1-3-2-4-5-6,依次追尾插入每个任务i(i=3,2,4,5,6)。反向调度与正向调度的求解方向相反,从调度序列1-3-2-4-5-6中最后一个任务n=6开始,倒序逐个安排任务i(i=5,4,2,3,1)。交替正向与反向调度,结合标准化编码更新,通过双向编码调整可开发出更优的解。为了避免算法陷入局部最优,当种群最优解持续未改进时,采取精英保留以及其他个体编码重建的策略,增加种群多样性扩大搜索空间,进一步提高全局寻优能力。


2.png

图1 个体编码与任务调度顺序


如图2所示,从较难的J3013中抽取案例进行试验分析,同时采用双向调度、标准化编码调整及避免局部最优策略,算法能在100代以内准确求出最小工期为58,收敛速度快且性能稳定。


image005.png

图2 单个实例求解迭代过程


表1 ADDE-BS算法结果

image006.png


表2 与其他文献算法平均偏差率(%)比较

image007.png


如表1所示,最大调度次数不超过50000时,J30平均偏差率很小且不超过0.01%,对于99%以上的问题实例,算法都能稳定求得PSPLIB给出的标准最优解。如表2所示,收集了最近几年其他文献的RCPSP算法平均偏差率,算法覆盖了遗传、差分进化、粒子群、蚁群、多Agent优化等。实验结果显示,5000次与50000次调度计算规模以内,本文J30问题平均偏差率0.01%已处于排行榜前列,50000次调度计算规模以内,本文的J60、J90、J120平均偏差率显著低于其他文献结果。由此表明,对于不同规模的RCPSP,ADDE-BS具有较好的泛化求解能力,并且显示出一定的优越性。

引用格式:项前, 周亚云, 吕志军. 资源约束项目的改进差分进化参数控制及双向调度算法. 自动化学报, 2020, 46(2): 283-293.


链接:http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c170728


作者简介


项前,东华大学机械工程学院副教授.主要研究方向为计算机集成制造系统,计算智能.

E-mail: xqsir@dhu.edu.cn


周亚云,东华大学机械工程学院硕士研究生.主要研究方向为计算机集成制造系统.本文通信作者.

E-mail: zhouyayun@mail.dhu.edu.cn


吕志军,东华大学机械工程学院副教授.主要研究方向为专家系统,智能检测.

E-mail: lvzj@dhu.edu.cn




https://wap.sciencenet.cn/blog-3291369-1232727.html

上一篇:无人飞行器集群智能调度技术综述
下一篇:JAS多名作者入选2019中国高被引学者榜单
收藏 IP: 103.254.68.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 01:51

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部