资源描述：
《基于petri网的启发式生产调度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第28卷第5期自动化学报Vol128,No152002年9月ACTAAUTOMATICASINICASept.,2002短文基于Petri网的启发式生产调度薛雷郝跃(西安电子科技大学微电子研究所西安710071)(E2mail:hopexuel@hotmail.com)摘要提出一种新的柔性制造系统调度方法.该方法可以通过引入测试弧增强普通Petri网的建模能力,可以对系统中的设备维护、设备优先级以及操作优先级进行建模,并进一步利用搜索算法对模型的状态转换空间进行启发式搜索得到优化调度.文中的实例展示了
2、算法的有效性.关键词生产调度,柔性制造系统,Petri网,启发式搜索中图分类号TN43PETRINETBASEDHEURISTICSEARCHFORSCHEDULINGXUELeiHAOYue(InstituteofMicroelectronics,XidianUniversity,Xi′an710071)(E2mail:hopexuel@hotmail.com)AbstractThispaperprovidesanewschedulingmethodforflexiblemanufacturings
3、ystems(FMS).Throughintroducingthetestarctotraditionaltimed2placePetrinet,anewPetrinet,theextendedtimed2placePetrinet,isproposed.Itcanconciselyrep2resentnotonlygeneralfeaturesofFMS,butalsothedevicemaintenance,devicepri2ority,andoperationpriority.Bytheuse
4、ofsearchmethodtoreachabilitygraphofcon2structedmodels,theoptimizedschedulingisobtained.Experimentalresultsarepre2sentedtoshowtheeffectivenessofthemethod.KeywordsScheduling,flexiblemanufacturingsystem,Petrinet,heuristicsearch1引言在柔性制造系统(FMS)中,在满足工艺要求的前提下,
5、如何统筹安排各种不同工艺的[1]制造顺序、分配系统资源、获得优化的系统运行效率?这就是所谓的生产调度问题.针对调[2]度问题已经提出了很多方法,例如排队论模型、数学规划、系统仿真、控制理论等,但是这收稿日期2000208207收修改稿日期2001203212828自动化学报28卷些方法描述问题的能力很有限,所以寻找更加有效的方法是很有必要的.[3]Petri网(PN's)作为一种描述离散事件动态系统(DEDS)的强有力的图形化的数学工[4]具,被广泛地用来分析DEDS的系统性能.在文献中接触到的与生产
6、调度有关的PN's研[5]究中,Shih和Sekiguchi在利用PN's仿真FMS功能的过程中利用局部调度解决冲突;[6]3Lee和DiCesare用人工智能的算法A给出了一个解决生产调度问题的框架;Sun和[7]3Cheng对Lee的方法进行了改进,提出了有限扩展的A算法.共同的不足是,首先是柔性制造系统中存在的设备故障、定期维护、设备的优先级和操作的优先级等都是影响系统性能的不可忽略的重要因素,而以上研究在模型上没有考虑它们,因此得到的调度在实际系统中不能获得预期性能;其次,他们的评估函数都是单
7、目标的,而实际生产系统的性能是由多目标决定的,所以多目标评价函数更具实际意义.本文的研究正是针对以上不足,给出了一个实用有效的调度方法.2模型的建立普通PN's只能描述系统的控制结构,而不能描述系统随着时间演变的特性,为了支持系统性能研究,本文在确定时间PN's(DTPN’s)基础上提出一种增强DTPN’s模型.定义1.增强DTPN’s是一个七元组N=(P,T,I,O,H,+,mo),其中P={p1,p2,⋯,pm}是有限的Place集合,m>0,T={t1,t2,⋯,tn}是有限的Transitio
8、n集合,n>0,满足P∪T=Á且P∩T=Á,I:P×T→N是P到T的输入函数,O:P×T→N是T到P的输出函数,H:P×T→N是P到T的测试函数,Ý+:P×R∪{0}是给P的每个元素定义一个操作时间的时间函数,Ýmo:P→I∪{0}是定义从P到正整数集合的初始标记函数.运行规则是,t∈T在标记m被使能当且仅当(Pp∈P,m(p)≥I(p,t))∧(Pp∈P,H(p,t)≠0,m(p)
