基于DE算法求解AGV作业调度问题研究
156 浏览量
2020-06-20
19:20:20
上传
评论 1
收藏 249KB PDF 举报
第
４
５
卷
第
４
期
２０１４
年
７
月
太原理工大学学报
ＪＯＵＲＮＡＬ
ＯＦ
ＴＡＩＹＵＡＮ
ＵＮＩＶＥＲＳＩＴＹ
ＯＦ
ＴＥＣＨＮＯＬＯＧＹ
Ｖｏｌ．４
５ Ｎｏ．４
Ｊｕｌ
ｙ
２０１４
文章编号
：
１０
０７
－
９４３２
（
２０
１４
）
０４
－
０５２６
－
０６
基于
ＤＥ
算法求解
ＡＧ
Ｖ
作业调度问题研究
杨锋英
，
刘会超
（
黄淮学院 信
息工程学院
，
河南 驻马店
４６３０００
）
摘
要
：
ＡＧＶ
作业调度问题
在一定约束条件下可建模为一个
ＮＰ
完全的多重
ＴＳＰ
问题
。
为了优化
ＡＧＶ
作业调度的效果
，
提高
ＡＳ
／
ＲＳ
系统的运行效率
，
本文提出用差分演化
（
ＤＥ
）
算法来求解
ＡＧＶ
作业
调度问题
，
并针对问题的特点对
Ｄ
Ｅ
算法进行了若干改进
。
设计了新的个体两段编码方法
，
提出了基于
生存时间的种群多样性增强机制来提高算法的搜索能力
，
避免陷入局部最优等
。
模拟结果显示
，
提出的
算法可以有效求解
ＡＧＶ
作业调度问题
，
获得了高质量的优化解
，
且收敛速度快
。
关键词
：
自动导航小车
；
作业调度
；
差分演化
；
智能算法
；
多重
Ｔ
ＳＰ
中图分类号
：
ＴＰ３０１．６
文献标识码
：
Ａ
随着柔性制
造需求的不断增长
，
许多企业建立
了集成生产的自动化立体仓库系统
（
ＡＳ
／
ＲＳ
，
Ａｕｔ
ｏ
－
ｍａｔｅｄ
Ｓ
ｔｏｒａ
ｇ
ｅ
ａｎｄ
Ｒｅｔｒｉｅｖａｌ
Ｓ
ｙ
ｓｔｅｍ
）。
其中
，
自动
导航小
车
（
ＡＧＶ
，
Ａｕｔ
ｏｍａｔｉｃ
Ｇｕｉｄｅｄ
Ｖｅｈｉｃｌｅ
）
作为
仓库出入
库作业的主要执行者
，
成为连接仓库和生
产车间的重要纽带
。
作业调度就是将用户提交的多
个作业进行重新排列并分配给合适的自动化搬运设
备执行
，
使作业的整体运行时间最少
［
１
］
。
作业调度
是一
种逻辑层次的全局调度
，
他具有管理和协调各
种搬运 设 备 的 作 用
。
在 集 成 生 产 的
ＡＳ
／
ＲＳ
环 境
中
，
ＡＧ
Ｖ
运送是作业执行中最重要
、
最耗时的
环节
。
因此
，
ＡＧＶ
作业调
度问
题对整个
ＡＳ
／
ＲＳ
的运行
效
率具
有决定性影响
。
在
ＡＳ
／
ＲＳ
相关 的
各优
化 领域中
，
目 前关于 巷
道分拣系统的存取优化
［
２
］
和
ＡＧＶ
在自由
空间
的路
径规划优化
［
３
－
５
］
的研究 较多
。
关
于
ＡＧＶ
调度 的
研
究多
把
ＡＧＶ
放到流
水线
作业环境中考虑
，
并将问
题建模为
ＦＳＳＰ
（
Ｆｌ
ｏｗ
Ｓｈｏ
ｐ
ｓ
Ｓｃｈｅｄｕｌｉｎ
ｇ
Ｐｒｏｂｌｅｍ
）
问题 进 行 求
解
［
６
］
。
甘 剑 锋 等
［
６
］
用排队论理论将
ＡＧＶ
调度系
统建
模为一个
Ｍ
／
Ｇ
／
１
模型
，
并用该模
型对
ＡＧＶ
调度效
率进
行了分析
。
金芳等
［
７
］
则基于
排队论
将
ＡＧＶ
调度系
统抽
象为一个
Ｍ
／
Ｍ
／
１
模型
，
并分析了模型的调度效率
。
雷定猷等
［
８
］
从柔性制造
的
一般环境出发建立了一个多
ＡＧＶ
多请求
的一
般
优化模型
，
并尝 试 用遗 传 算 法 进 行 求 解
。
文 献
［
９
－
１０
］
简化了
ＡＧＶ
调
度的
相关
约束
，
建立了相应的优
化模型
，
并分别提出用遗传算法和粒子群算法进行
求解
。
实际上
，
集成生产 环境中的
ＡＧＶ
作业调
度
和
ＦＳ
ＳＰ
问 题
并 不 完
全 相 同
。
总 体 来 说
，
目 前 对
ＡＧＶ
作业调
度问
题的研究还很不成熟
，
在问题模型
和求解算法方面还需要更深入的研究
［
１
］
。
差分演化
（
ＤＥ
）
算
法是模拟大自然的演化过程而
提出的一种基于种群的随机搜索算法
［
１１
－
１２
］
。
自提出
以来
，
该算
法因其简单
、
有效和鲁棒性强等优点受到
广泛关注
，
并应用在很多优化领域
［
１３
］
。
文献
［
１４
－
１５
］
尝试用
ＤＥ
算法
来求解
ＡＧＶ
调度问
题
，
但问
题模型
仍然是基于
ＦＳＳＰ
，
而且
仅采用
了经 典的
ＤＥ
算法
。
本文首次尝试用改进的
ＤＥ
算法来求解
ＡＧＶ
作业调
度
问题
。
首
先基于合理约束建立了问题的静态优化
模型
，
并分析了模型的性质和求解难度
。
其次
，
针对
调度任务的双重性
，
提出了新的个体两段编码方法及
对应的适应度评价方法
；
并针对
ＤＥ
算法容易陷入局
部最优的问题
，
提出基于生存时间的个体重置机制来
增强种群多样性
。
模拟结果显示
，
提出的算法可以有
效求解
ＡＧＶ
作业调
度问
题
，
且收敛速度快
。
１
ＡＧＶ
作业调
度模
型
１．１
ＡＧＶ
作
业调度问
题
在集成生产的
ＡＳ
／
ＲＳ
环境中
，
Ａ
ＧＶ
的
任务
就
是接收管理系统的调度在仓库
和工作间之间运送货
收稿日期
：
２０
１３
－
１２
－
２０
基金项目
：
河南省科技攻关计划资助项目
（
１１２１０２２１０３８３
）；
河南省基础与前沿研究资助项目
（
１２２３００４１００７１
）
；
驻马店市科技攻关计划资
助项目
（
１１３１４
）
作
者
简介
：
杨锋
英
（
１９７９－
）
，
女
，
河南南阳人
，
讲
师
，
硕士
，
主要从事计算机网络
、
智能计算等研究
，（
Ｅ
－
ｍａｉｌ
）
ｚｉ
ｙ
ｉ
ｎ
ｇ
６６１
＠
１６３．ｃｏｍ
DOI:10.16355/j.cnki.issn1007-9432tyut.2014.04.026
中国煤炭期刊网
www.chinacaj.net
评论0
最新资源