贪心优化的搜索算法在RGV动态调度中的应用

发布时间：2021-01-11 17:29

　　随着计算机领域的飞速发展,物流等行业也开始向自动化、智能化、无人化的方向发展。智能RGV动态调度是智能加工系统的重要环节,合理的调度方案能够大大提高系统的作业效率。针对RGV调度问题,建立了基于自动化加工系统的动态调度模型。提出了一种基于贪心策略优化后的搜索算法,通过贪心选择最可能发生的情况,可减少搜索的复杂度,从而达到在极短时间内接近最优调度的目的。通过仿真实验,对先后进行2道工序的CNC进行优化配对,以产量最大作为目标,搜索得到CNC的最佳分配方案,达到了接近最优解的调度策略。在规定的工作时间内,使用贪婪优化算法提高了搜索的有效性,使RGV系统能够高效调度,验证了贪心优化算法的可行性和有效性。 

【文章来源】：沈阳师范大学学报(自然科学版). 2019,37(04)

【文章页数】：6 页

【部分图文】：

图２贪心优化的搜索调度流程图Ｆｉｇ．２Ｇｒｅｅｄｙｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｈｅｓｅａｒｃｈｓｃｈｅｄｕｌｉｎｇｆｌｏｗｃｈａｒｔ

择［９］。在贪婪算法中，无需从整体最优的目标上加以考虑，需要求出的是某一时刻某种意义的局部最优解。由于考虑的片面性，贪心算法无法对所有问题求得整体最优解［１０］。算法核心是贪心策略的选择，局部选择的贪心策略需要独立于其他状态，即当前选择与之前状态无关且不影响之后的状态，只与当前状态有关。２．２贪心优化分析在计算机算法分析中，广度优先搜索的时间复杂度为Ｏ（Ｖ＋Ｅ），其中Ｖ是节点的数目，Ｅ是变的数目，如图３所示。图３ＢＦＳ在ＲＧＶ调度中可能的情况Ｆｉｇ．３ＰｏｓｓｉｂｌｅｃａｓｅｓｏｆＢＦＳｉｎＲＧＶｓｃｈｅｄｕｌｉｎｇ第４期罗敏娜，等：贪心优化的搜索算法在ＲＧＶ动态调度中的应用７１３

在本文提出的算法中，Ｖ每次执行完指令后，后续有４种可能存在的操作，此时节点数将会以指数增长，复杂度将会高于Ｖ，当系统需要长时间运行，ｎ（ＲＧＶ操作的次数）过大时，计算机将无法完成如此巨大的计算。ＢＦＳ产生如此巨大计算量的原因是，ＲＧＶ每次调度都有４种可选的新路径，造成了时间指数增长的情况，因此可以贪心选择其中在全局动态性上最可能成为最优路径的０～２条路径（如图４所示），作为下一步可能出现的情况。在图４中，虚线部分为排除掉不进行后续计算的路径，这样将大大减少计算耗时，并且也能达到非常良好的效果［１１］。图４贪心选择后可能出现的情况Ｆｉｇ．４Ｔｈｅｃａｓｅｔｈａｔｍａｙｈａｐｐｅｎａｆｔｅｒｇｒｅｅｄｙｃｈｏｉｃｅ２．３贪心优化根据对每台ＣＮＣ当前状态与未来状态之间关系的考虑，给每一个位置设计了一种对其最近２台ＣＮＣ未来状态及周围ＣＮＣ的状态进行综合考虑的性能评价标准［１６］。在ＲＧＶ每次操作后，更新４个位置的性能权值，权值基于２个超参数由其未来运行后的状态来定，即目标最近２台ＣＮＣ的剩余时间减去运动花费时间，再将其与做乘积运算，最后加上与目标附近４台机器（对于１和４位置只有２台）运动后的状态平均值的乘积［１７］。超参数可以不断拟合，使这种评价标准发挥良好的效果［１２］。将上述的评价标准转化为数学模型，即Ｗｉ的函数为Ｗｉ＝α｛ａｂｓ（ＵＴｉ－ｄｉｓＬｉ）＋

【参考文献】：
期刊论文
[1]基于改进A*算法优化的移动机器人路径规划研究[J]. 陈豪,李勇,罗靖迪.  自动化与仪器仪表. 2018(12)
[2]可变线路公交车辆调度算法优化研究[J]. 邵孜科,张泉,王树盛,张小辉,李文权.  交通信息与安全. 2018(05)
[3]公交立体车库调度算法的研究与实现[J]. 宋扬,田野,苏睿聪,陈星,宫瑞泽.  自动化博览. 2018(10)
[4]RGV系统设计与应用[J]. 刘俏.  物流科技. 2016(05)
[5]基于遗传算法和贪婪算法的作业车间调度[J]. 王新,贾志强,尚宏美.  机械工程师. 2015(01)
[6]基于FCFS策略的带时间窗车队调度问题研究[J]. 轩华.  交通运输系统工程与信息. 2013(06)
[7]结合广度搜索的遗传算法在水库调度中的应用[J]. 张忠波,张双虎,蒋云钟.  南水北调与水利科技. 2011(05)
[8]几种经典搜索算法研究与应用[J]. 欧阳圣,胡望宇.  计算机系统应用. 2011(05)
[9]贪心算法的探讨与研究[J]. 常友渠,肖贵元,曾敏.  重庆电力高等专科学校学报. 2008(03)
[10]贪心算法在多机调度问题中的应用[J]. 董春平.  电脑开发与应用. 2007(10)

博士论文
[1]基于离散事件的列车调度问题模型与算法研究[D]. 徐小明.北京交通大学 2016



本文编号：2971191