基于死锁避免策略的柔性制造系统无死锁调度

《基于死锁避免策略的柔性制造系统无死锁调度》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于死锁避免策略的柔性制造系统无死锁调度对于致力于多品种小批量的柔性制造系统生产來说，调度问题和死锁问题一直是研究的两个重点。由于计算复杂度的原因，这两个NP—hard问题始终没有彻底的解决方案，现有的很多研究成果都是对它们分别进行讨论，然而事实上，对于资源冇限的柔性制造系统，如果不考虑死锁问题，调度很可能是不可行的。因此我们将死锁问题集成在调度问题中，提出了一种基于死锁避免的柔性制造系统无死锁调度方案。本文主要针对无缓冲区的柔性制造系统提出一种基于集束搜索方法和改进银行家算法的新的无死锁调度方案，

2、目标是找到一个可行的资源分配顺序使得系统在无死锁的情况下实现有效调度，同时尽量减少总加工时间，即最优化调度结果。尽管在无缓冲区的柔性制造系统屮常常会产生无死锁不安全状态，我们也可以通过减小银行家算法中的最大资源需求和回溯步骤在非常短时间内找到一个合适的调度方案得到一个较好的调度结果。该算法可以解决复杂调度系统问题，折衷了调度时间的消耗和调度结果的质量。关键i司：柔性制造系统，冇向图，无死锁调度，集束搜索，银行家算法DEADLOCKFREESCHEDULINGFORFMSBASEDONDEADLOCK

3、AVOIDANCEPOLICIESABSTRACTFlexiblemanufacturingisveryimportantintoday^sMulti-varietysmall-lotproduction.SchedulingandDeadlockinFMSsaretwohotresearchtopics.Duetothecomputationcomplexity,thetwoNP-hardproblemsstillhavenoexhaustivesolution.Muchresearchworkd

4、ealtwiththesetwoproblemsseparately.However,intherealworld,schedulingwillbeunfeasibleifdeadlockexistsinthemanufacturingsystemwithlimitedresources.Thus,consideringdeadlockinschedulingproblems,wepresentefficientdeadlockfreeschedulingalgorithmsbasedondeadl

5、ockavoidancepolicies.ThispapermainlyconsidersFMSwithoutbuffersandproposesanewkindofdeadlockfreeschedulingmethodbaseonbeamsearchandmodifiedbanker^algorithm.Theobjectofschedulingmethodconsistsinfindingafeasibleresourceallocationsequencetominimizethemakes

6、panandtoavoidthedeadlocksituation.Evenifthedeadlockfreeunsafestateswilloccurfrequentlyinthosewithoutbuffersystems,themodifiedbanker'salgorithmcanstillfindafeasiblescheduletoavoiddeadlocksuccessfullywithdeducedmaximumresourcesclaimandbacktrackingstepsin

7、averyshorttime.Itmayresolvemostofcomplexschedulingproblems,andhaveatradeoffbetweencomputationexpenseandsolutionqualityformanufacturingsystem.KEYWORDS:FlexibleManufacturingSystem(FMS),TransitionDiagraph,DeadlockFreeScheduling,BeamSearch,ModifiedBanker's

8、Algorithm上海交通大学硕士毕业论文上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文屮已经注明引用的内容外，木论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重耍贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：黄文婷H期：2008年2月18日in上海交通大学硕士毕业论文上海交通大学学位论文版权使用授权书本学位论文作