当前位置 : 网站首页 > 新闻中心

2019

10-16


来源:

浏览: 6

作者:

基于模因算法的作业动态调度策略研究
目前,国内外研究动态调度的主要方法有三种,即人工智能,专家系统方法和仿真。从算法流程图可以看出,Memetic算法采用了与遗传算法相似的框架,但不仅限于简单的遗传算法,充分吸收了遗传算法和局部搜索算法的优势。它不仅具有强大的全局优化能力,而且还可以在每次交叉和变异后执行局部搜索。通过优化总体分布,尽早消除不良总体,从而减少迭代次数,加快算法速度并提高算法解决方案的质量。 。在Memetic算法中,局部搜索策略非常关键,它直接影响算法的计算效率。滚动窗口也称为滑动窗口,其主要思想是优化滚动分区,静态动态问题并离散化连续问题。具体的操作流程如下:在初始时刻,在所有具有加工条件的可调度工件集中定义了要处理的工件的子集,即工件窗口,并将该子集从可调度集中删除,然后优化窗口中的工件。根据调度方案进行处理,直到满足触发机制为止,然后重新更新窗口,并重复上述过程。它将动态调度过程分为多个调度时刻。当调度时刻到来时,根据当前生产状态选择调度方案。它放弃了全局优化的概念,在线优化每个调度间隔,并使系统在此间隔内达到最优,从而使调度方案能够适应复杂,动态的环境。窗口工件的选择规则和重新计划周期的确定是滚动窗口实施的关键,这直接影响到计划优化的整体效率。窗口工件的数量会影响调度优化的效果。如果选择的工件太少,则优化调度的总体效果不理想,机床利用率也很低。如果选择的工件太多,则紧急情况的响应时间会更长。它影响车间的生产率,因此选择正确数量的工件非常重要。通常,驱动策略具有三种类型:事件驱动策略,周期驱动策略和基于周期和事件的混合驱动策略。事件驱动策略是指在发生更改系统状态的事件时立即重新计划。周期驱动策略根据先前设置的时间执行每隔一个生产周期的重新计划。事件驱动策略可以处理紧急情况,但缺乏对未来事件的预测能力,也没有整体概念。周期驱动的策略可以提高生产的稳定性,但是它们不能处理紧急情况。基于周期和事件驱动的混合驱动策略结合了前两种策略的优点,不仅可以很好地响应实际的动态环境,而且可以保持一定的稳定性。因此,本文采用基于周期和事件的混合驱动策略。 3基于模因的动态调度算法3.1染色体编码和解码本文采用基于过程的编码方法,即每个工件过程由相应的工件编号表示,并且每个工件编号都等于操作的总数工件,然后根据染色体出现的顺序进行编译,第k次出现的工件编号表示该工件的第k个过程。对于动态调度问题的解码,通常可以通过两种方式对其进行处理:半主动调度和主动调度。本文采用插件式贪婪解码算法,可以确保染色体被解码并产生主动调度,确保解码后的解是可行的解,从而减少了搜索空间,提高了计算效率。解码算法描述如下:该过程按顺序进行,第一个过程是首先安排顺序,然后进行顺序中的第二个过程,并将可行的处理时间插入到相应的机器中。以这种方式进行处理,直到序列中的所有过程都安排在一个可行的位置。 3.2跨策略对于基于过程编码的动态调度问题,本文采用顺序交叉策略,该策略可以保留父级中的局部排列并可以融合不同新排列的有序结构,从而增加了种群的多样性。从而提高交叉效率。该分频器1828的操作如下:后代1直接继承亲本1中阴影所示的基因串,并且在删除继承的基因之后,亲本2删除剩余的基因位置。 (阴影所示)按顺序填充,并且相同的子代2直接继承父代2中父代显示的基因串,在删除继承的基因后,其余基因被父代1中的基因删除。填充以产生子代2。3.3 4x3调度问题的变异策略在解决车间调度问题时,常用的变异算子具有交换变异,插入变异和逆变换。本文采用了一种基于邻域搜索的新型变异算子,通过邻域搜索增加了种群的多样性,提高了后代的性能。具体步骤是:随机选择三个不同的点Pi,P2,P3,根据这三个点的不同排列,可以生成另外五个不同的邻域染色体,并比较每个染色体的适应度值,适应度为如图所示,染色体被保留为孩子的变体。有许多本地搜索策略可以解决调度问题。本文使用改进的模拟退火搜索算法。在传统的模拟退火算法中,通常将初始退火温度to设置得很高,并且冷却速率At很慢,导致迭代太多,因此计算量很大。本文采用了一种改进的模拟退火搜索策略。当温度高时,冷却速率大。当温度低时,冷却速率小。这不仅保证了算法的全局搜索能力,而且加快了算法的收敛速度。该算法的操作如下。 1将初始温度设置为确定温度t,冷却速率At和冷却系数a2以比较染色体适应度A = /(X,+ i)-/(X,),其中/(X,)代表ith交叉或突变后的染色体适应度值,如果随机数(0,1),则接受交叉或突变,终止算法,否则拒绝,重新交叉或突变,3改变退火温度,使t + i 4仿真和分析仿真调度实例由于动态调度问题,目前尚无标准研究。因此,基于FT10问题,适当地添加了一些动态数据。动态数据主要包括伪像延迟和紧急插入两种类型,然后根据这些测试数据确定其完成时间。它是930个时间单位,该调度方案将用作后续动态调度的初始方案。 4.1.2工件延迟重新安排本节仅讨论工件延迟问题。假设在生成初始计划后,在第480时间单位中,发生紧急动态事件以延迟工件。具体的动态事件是:由于机器故障,丢失的工作或其他原因,机器3上的过程(9、5)的处理时间被延迟了30个时间单位,这是由于提前交货,过程(7, 8)的机器9必须提前20个时间单位处理。此时,由于发生了两个动态事件,因此需要执行重新计划。 Memetic算法用于在480个时间单位后重新安排所有操作。显示了调度优化方案,运行时间为23s,完成时间为979次。单元。随着时间的推移,在第550时间单位中,发生了紧急事件。由于工人蹲下等原因,机器4上的过程(4、8)与过程(2、5)交换,并且由于提前交货,机器上的过程(7、9)也要交换e 8必须在处理之前(5,8)。此时,由于发生了两个动态1829事件,因此需要重新计划。 Memetic算法用于在550个时间单位后重新调度所有进程,运行时间为16s,完成时间为989个时间单位。使用Memetic算法对第500个时间单位后的未加工工件和新的紧急工件进行重新调度,显示了新获得的调度优化方案。重新优化时间为21s,完成时间为1018个时间单位。 4.1.3调度插入重新安排表1加工机器和多余工件的加工时间本节仅讨论紧急插入的问题。假设在生成初始调度后,以500个时间单位发生了新的紧急动态事件,即新工件11和工件12的紧急插入。表1显示了这两个紧急工件的加工机器和加工时间。初始调度优化方案Gabga¢:紧急调度后第480时间单元的重新调度方案中调度点的重新调度方案4.2通过对工件时延和紧急事件两种动态事件的调度实验研究进行结果分析从结果中进行插入可以得出以下结论:1使用滚动窗口技术,可以将复杂的动态调度问题分为多个连续的调度子间隔。通过优化每个调度子间隔,调度方案可以适应复杂的动态环境变化的需求。解决动态调度问题是一种可行的策略。 2在动态事件发生后的重新调度方案中,可以将完成时间控制在一个良好的范围内,并且重新优化操作时间也比较合理,这表明Memetic算法是解决调度优化问题的有效算法, 3考虑到动态调度问题的多样性,本节仅讨论两个动态事件的处理,但是该策略具有很强的通用性,可以应用于其他动态事件。调度问题的解决方案。结论本文针对研讨会的动态调度问题,重点讨论了两种动态事件:工件延迟和调度,并提出了一种基于Memetic算法的动态调度策略。使用周期性和事件驱动的混合重新调度策略,并使用滚动窗口策略,将动态调度过程分为连续的静态调度间隔,并使用Memetic算法在每个间隔中进行调度优化,从而使调度方案能够适应复杂的动态环境。变更要求。最后,通过在改进的Job-shop基准上进行的实验验证了该策略的可行性和有效性。
分享到: