资源描述：
《柔性制造系统中的无死锁调度》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、上海交通大学硕士学位论文柔性制造系统中的无死锁调度姓名：施湘琼申请学位级别：硕士专业：控制理论与控制工程指导教师：吴智铭20060201上海交通大学硕士学位论文柔性制造系统中的无死锁调度摘要柔性制造在当今追求多品种小批量的生产中具有相当重要的地位多年来很多专家学者致力于关于柔性制造的理论和方法的研究柔性制造系统中的调度问题和死锁问题一直是两个研究热点他们是两个独立的NP-hard问题由于计算复杂度的原因始终没有彻底的解决方案很多现有的研究成果都是对他们分别进行讨论而事实上在资源有限的柔性制造系统中如果不考虑死锁问题调度很可能是不可行的因此
2、我们将死锁问题集成在调度问题中提出了一种无死锁调度方案针对柔性制造系统有缓冲区和无缓冲区两种情况我们分别提出了基于启发式规则的无死锁调度算法该算法基于集束搜索方法局部评价函数和全局评价函数在没有缓冲区的制造系统中常常会产生无死锁不安全状态因此当系统遇到死锁时将采用回溯步骤使系统恢复到以前状态在有缓冲区的制造系统中不存在无死锁不安全状态所以只需采用单步前瞻的无死锁预防策略就可以保证系统运行于无死锁状态下因此也不需要回溯步骤因为两种方法都是基于启发式的规则他们需要的计算时间很短适合在线运行总之他们是折衷了计算时间的消耗和调度结果的质量的算法关
3、键字Petri网变迁有向图无死锁调度FMS集束搜索上海交通大学硕士学位论文ABSTRACTFlexibleManufacturingisveryimportantintoday’sMulti-varietysmall-lotproduction.Inrecentyears,manyexpertshavebeendevotedtotheresearchofthetheoryandmethodsinFlexibleManufacturing.SchedulingandDeadlockaretwohotresearchtopics.Sincet
4、heyarebothNP-Hardproblems,duetothecomputationcomplexity,thereisstillnoexhaustivesolution.Muchresearchworkdealtwiththesetwoproblemsseparately.However,intherealworld,schedulingwillbeunfeasibleifdeadlockexitsinthemanufacturingsystemwithlimitedresources.Thus,consideringdeadlo
5、ckinschedulingproblems,wepresentefficientdeadlockfreeschedulingalgorithms.Inthispaper,wepresentheuristicdeadlockfreeschedulingalgorithmsforflexiblemanufacturingsystemswithbufferandwithoutbufferrespectively.Thealgorithmsarebasedonbeamsearch,localevaluationruleandglobaleval
6、uationfunction.Insystemswithoutbuffer,deadlockfreeunsafestateswilloccur,therefore,backtrackingstepswillbeexecutedincasesystemsgetintodeadlock.Insystemswithbuffer,nodeadlockfreeunsafestatesexit,thus,withaone-steplook-aheaddeadlockavoidancepolicy,systemsareensuredtoruninsaf
7、estates.Therefore,therearenobacktrackingstepsinthecorrespondingalgorithm.Sincethealgorithmsarebothbasedonheuristicmethods,theyinvolve上海交通大学硕士学位论文smallon-linecomputationconsumption,thus,theyaresuitableforrealtimeimplementation.Theyprovideatradeoffbetweencomputationexpensea
8、ndsolutionquality.KEYWORDS:PetriNet,TransitionDigraph,DeadlockFreeScheduling,FMS,BeamSearchSHANG
