基于petri网仿真的双资源jsp动态优化调度

1、基于Petri网仿真的双资源JSP动态优化调度摘要:以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,通过构建Petri 网控制器使系统的运行满足期望的目标,同时利用混合遗传算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等资源制约条件下的动态优化调度.为了保证生产的平稳性,最大限度地维持车间的生产能力,提出了针对不同的扰动进行分类处理的新方法,首先基于机床故障修复时间、工人离岗时间及取消订单包含任务的多少进行分类调度,然后根据机床故障修复后以及工人回岗后剩余任务的多少决定是否进行再一次的调度,最后对算法进行了仿真研究.关键词:Petri网;控制器;遗传算法;模

2、拟退火算法;动态车间调度Abstract: A Petri net with controller is used to model discrete events in flexible job shop scheduling, and making the system running satisfy the anticipant aim through constructing the Petri net controller, and the scheduling results is obtained based on hybrid algorithm of genetic algo

3、rithm and simulated annealing algorithm. The method is developed to address the dynamic scheduling problem in manufacturing systems constrained by machines, workers. In order to assure the stability of manufacture, and the job shop production ability can be maintained farthest, different uncertain d

4、isturbances are classified to dispose with a new method. Firstly, classified based on machine repairing time, and worker leaving time, and task of order canceling; and then deciding whether it is arranged again based on remainder task after machine repairing and worker returning; and lastly, simulat

5、ion based dynamic job shop scheduling is developed. Key words: Petri net; controller; genetic algorithm; simulated annealing algorithm; dynamic job shop scheduling前言具有柔性加工路径的Job shop型调度问题(JSP)是一个具有 NP 难计算复杂性的开放问题.虽然针对调度问题已经提出了很多方法,例如排队论模型、数学规划、系统仿真、控制理论等,但是这些方法描述问题的能力很有限,所以寻找更加有效的方法是很有必要的.近年来,Petri网

6、作为离散事件动态系统的建模和分析工具,已被成功地应用于柔性生产系统的建模/分析和控制 1-6,但都只是对生产线本身建模,不能反映作为生产线中外部控制的调度策略的影响. 本文应用具有库所和变迁混合约束的Petri网控制器设计方法7进行控制器的设计,并对Petri网进行建模.在此Petri网模型基础之上充分地利用了混合的遗传算法和模拟退火算法8(GASA),通过对该Petri网模型的仿真运行可以获得调度策略的性能.为了更好地解决动态调度问题,提出了对双资源动态优化调度进行分类处理的新方法,针对不同的扰动通过选取合理有效的调度策略,最大限度地维持车间的生产能力,通过具体实例验证了所提方法的问题求解能

7、力,表明所提出方法的有效性.柔性生产调度的Petri网模型普通Petri网模型仅能够反映生产线的加工路径及其资源约束,而本文通过构建Petri网控制器可以对设备优先级、操作优先级等进行描述.添加控制器的目的就是使系统的运行满足期望的目标,从控制的观点来看,控制器是通过使能或禁止它的输出变迁来实现它的控制目标的,并从它的输入变迁的激发获得反馈,所以该控制器设计方法只需要考虑直接或间接的与约束有关的变迁,同时利用局部设计和Petri网简化技术实现控制器的设计,因而比Yang9提出的 Petri 网控制器设计方法更加简单、有效并且不会导致死锁.为了直观的说明柔性生产调度的Petri网模型,建立一子模

8、型.考虑如下的一个FMS系统,系统中有3种类型6台机床,1、2号机床为类型;3号机床为类型;4、5、6号机床为类型.共有10个工件需要加工,每个工件有14个工序,工人工作表、任务参数表如表1和表2.工件 工序 加工时间 机床类型 工件 工序 加工时间 机床类型1 1 12 5 2 10 2 9 3 10 3 5 4 8 2 1 6 6 1 6 2 6 7 1 6 3 8 2 8 3 1 5 8 1 12 2 9 2 8 4 1 4 3 8 2 6 9 1 5 3 10 2 8 5 1 5 10 1 7 工人 机床1 机床2 机床3 机床4 机床5 机床61 操作 操作 2 操作 操作 3 操作

9、 操作4 操作 操作建立工件1的Petri模型如图1所示,其中各符号的意义:表示第i个工件的初始状态;表示第i台机床;表示第i个工件的第j个操作由第h个工人在第k台机床上进行;表示操作开始;表示操作结束;表示工件i的第j个操作结束后的缓冲区;表示第i个工件加工完成.虚线部分表示控制器部分(具体设计步骤见参考文献7),它主要对以下两种行为进行控制:第一个缓冲区不能上溢也不能下溢,当缓冲区内有工件时机床3不能启动操作,即;机床3有比机床1修复和回到正常工作(忙状态)的优先级:在两台机床同时坏掉的时候,机床3应优先被修复.按照此方法可以依次建立其余工件的Petri网模型,最后将这些模型通过表示机床、

10、工人的资源库所联结起来,便得到系统的整个模型,由于图形巨大,在此予以省略.调度数学模型的建立研究的调度模型是:作业车间需要加工多种工件,每种工件有多条工艺加工路线;要求制定出一个生产计划,它不仅为每一个工件决定一条工艺加工路线,而且还必须满足整个车间的生产周期最短.调度的目标为min Z (1)约束条件如下:零件i的第j条工艺加工路线中的最后一道工序(2) 零件i的第j条工艺加工路线中的非最后一道工序(3)零件i的第j条工艺加工路线中的第一道工序(4)零件i的第j条工艺加工路线和零件p的第q条工艺加工路线中都有工序要在机床设备m上加工(5)(6)所有零件只能有一条工艺加工路线被选中(7)零件i

11、的第j条工艺加工路线中的任何一道工序(8)零件i的第j条工艺加工路线和零件p的第q条工艺加工路线中都有工序由工人w来加工(9)(10)式中,Z为生产周期(make-span);i为零件;j为属于一个零件的一条工艺加工路线;m为机床设备;h为零件i的某一条工艺加工路线的第h道工序;、分别为零件i的第j条工艺加工路线中的第h道工序在机床m上的加工时间和加工完毕时刻;H为非常大的正数;w为工人;、分别为零件i的第j条工艺加工路线中的第h道工序由工人w加工的时间和加工完毕的时刻;为机床m加工工序h和s的顺序判别条件,当工序h和s都在机床m上被加工时,如果零件i的第j条工艺加工路线中的第h道工序先于零件

12、p的第q条工艺加工路线中的第s道工序被加工,则=1,否则=0,为零件i的第j条工艺加工路线被选中的判别条件,如果选中,则=1,否则=0;为工人w加工工序h和s的顺序判别条件,当工序h和s都由工人w加工时,如果零件i的第j条工艺加工路线中的第h道工序先于零件p的第q条工艺加工路线中的第s道工序被加工,则=1,否则=0.如果零件i的第j条工艺加工路线在式(2)和式(7)的条件下被选中,则式(1)中的目标方程用来限制该工艺加工路线最后一道工序的完工时刻;式(7)确保每个零件只有一条工艺加工路线被选中;式(3)和式(4)确保对于一个指定的零件,在机床g上加工的顺序h-1先于在机床m上加工的下一道工序h

13、,式(5)和式(6)确保两道不同的工序不能同时在同一台机床上被加工,而且任何机床在任何时候都不能加工一道以上的工序;式(5)表示零件p的第q条工艺加工路线中第s道工序在机床m上先于零件i的第j条工艺加工路线中第h道工序被加工,而式(6)表示了相反的加工顺序;式(9)和式(10)确保两道不同的工序不能同时被一名工人加工,而且任何一名工人在任何时候都不能加工一道以上的工序.动态调度的分类处理根据车间实际工作的情况,研究的作业车间的动态环境包括:机床设备突然损坏;损坏的机床被修复;工人离岗;工人回岗;定单被取消.机床故障机床故障按其严重程度或所需修复时间长短笼统分为2大类,即机床大故障和机床小故障,

14、这样处理可以在仿真研究中屏蔽住不同的机床故障形式,因而也可以集中精力考虑如何进行故障调度.机床大故障(11)(12)为修复故障机床m所需要的时间;、为给定的正数,l为零件i所包含的工序数,k为机床m故障修复好以后零件i开始加工的工序.式(11)为机床大故障/小故障的判别条件,满足式(11)即为机床大故障,否则为机床小故障;式(12)用来判别机床故障修复好以后剩余任务的多少,是针对剩余工件的,如果满足式(12)则剩余任务较多,否则剩余任务较少.机床发生大故障时对工件的加工有较大影响,如果等待机床修复完成再继续加工,则很可能导致该批工件不能按时交货,因此必须为这些工件寻找其它的加工路径与设备,即满

15、足式(11)的故障机床退出生产后对余下的工件进行重新调度.机床故障被修复好以后根据剩余任务的多少来判断是否马上安排该机床进入到新的调度中:满足式(12)则剩余任务较多,机床马上被安排进行加工操作,即对剩余任务进行再次调度. 不满足式(12)则认为剩余任务较少,该机床就不再参与这次的调度进行加工,等该调度结束后再参与下一次的调度.否则,不但扰乱了原来的工人和机床的任务分配,而且由于剩余任务较少,调度结果与原来的相差不是很大.机床小故障如果机床故障修复时间不满足式(11)即机床发生小故障时,可以不去为故障机床上的工件另外寻找加工路径,而宁可让其等待该机床的修复,然后再重新进行加工.这样处理显然是以

16、局部的工件等待为代价来换取整体的协调有序.工人离岗工人离岗按其离岗时间长短分为工人长时间离岗和短时间离岗.(13)为工人w离开岗位的时间;为给定的正数,式(13)用来判别工人是长时间还是短时间离岗,如满足式(13)则是工人长时间离岗,否则是工人短时间离岗;工人长时间离岗需对余下工件进行重新调度,工人回归岗位后同样根据式(12)判别剩余任务的多少决定是否马上参与再调度,这时k为工人w回来以后零件i开始加工的工序,再调度的原理同机床大故障相同.工人短时间离岗处理方式同机床小故障相同.定单取消定单取消按该定单所包含任务的多少进行分类,即大定单和小定单.(14)f为该定单包含的工件数,式(14)用来判

17、断该定单是大定单还是小定单,如满足式(14)则认为是大定单,否则认为是小定单.取消大定单时需进行重新调度,否则很可能导致某些工人和机床有较长的空闲时间,从而使机床和工人的加工和操作能力发挥不足,降低了机床的利用率和工人的工作效率.小定单取消不需要重新调度,由于小定单工件加工时间较短,这类定单的取消对整个调度影响不大,如果采用与取消大定单相同的调度策略,则不仅调度结果差别不大,而且由于打乱了原有的调度方案,对工人和机床干扰很大.因此,在取消小定单时,可以不去为剩余的工件另外寻找加工路径,而让它们遵循原来的调度进行加工.仿真结果与分析对表1和表2所示的例子进行仿真运算.种群规模50,交叉率为0.8,变异率为0.1,退温指数=0.9,进化50代后得到的调度方案见图2(灰色表示机床/工人处于忙的状态,白色部分为机床/工人处于空闲状态),目标函数值为55.如果调度的最佳解不唯一,则该调度算法同样也可以将他们全部搜索到.该算例的最佳调度就不是唯一的,图2所示的只是其中的一个最佳调度的Gantt图和工人任务分配图.图2调度Gantt图显示了工序和机床的分配关系.图中横坐标表明了这批零件加工的时间历程,纵坐标表明了机床设备,不同的零件及工序用四个字