基于变迁可靠性与可维修性的Petri网主干路径寻优
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
自1962年C.A.Petri在博士论文中首先提出Petri网之后,人们就不断的对其进行理论延伸和改进。Petri网主干路径问题很早就受到人们的重视,主干路径是从输入库所到输出库所耗时最短的路径,它是贯穿系统的效率最高的路径,在一定程度上决定着系统的性能。现实生活中很多问题可以被模拟为Petri网主干路径的寻找问题。基本Petri网中变迁具有时间延迟的特性,以往的研究都是用时间延迟模拟影响主干路径的因素并寻找Petri网的主干路径。当情况复杂时,只能模拟单一因素的时间延迟特性并不能很好的模拟实际问题。本文经过对以往Petri网寻优理论的深入研究后提出一种变迁具有可靠性和可维修性的Petri网,影响Petri网主干路径寻找的因素不仅包括时间延迟,还有变迁的可靠性和维修性。
     本文围绕变迁具有可靠性和维修性这一主线对Petri网的主干路径寻找问题进行深入研究:
     文中首先分析了寿命服从威布尔分布的变迁的可靠性变化情况,在考虑可靠性和时间延迟的因素后建立随机Petri网模型,并用蚁群算法与Petri网结合的方法寻找主干路径,同时在选路策略、信息素更新、库所更新等问题上对蚁群算法进行改进,然后以数学形式提出变迁具有可靠性的Petri网主干路径寻优算法,实例证明了算法的正确性。
     不可维修的变迁仅仅具有可靠性,但是可维修的变迁不仅具有可靠性还具有维修性,综合考虑了可靠性与维修性的可用度是影响主干路径寻找的另一重要因素,本文随后又提出变迁具有可用度的Petri网主干路径寻优算法,该算法重新改进了蚁群算法并引入随机搜索托肯。在考虑了可用度、时间延迟和维修成本等多个影响因素后的蚁群算法在Petri网中进行路径寻找,实例证明算法能够找到主干路径。
     可靠性和维修性的分布函数是多样的,可以同时都服从指数分布,也可能服从不同的分布,可靠性服从威布尔分布且维修性服从对数正态分布的情况最贴近实际问题。在分析了可用度的计算方法之后,本文继而建立相应的Petri网模型,并用基于正态分布的路径选择算法、基于均匀分布信息量均衡算子的路径信息素更新策略和修改信息素的挥发因子等新方法对蚁群算法进行再改进,最后利用改进的蚁群算法来寻找到主干路径,实例证明算法能够解决实际问题。
     经过三次使用,蚁群算法与Petri网结合的理论已被证明是完全正确的,随后本文将这一理论应用到供应链网络的合作伙伴选择问题上,应用该方法在供应链网络模型中进行主干路径寻找,实例证明算法可以选择到最优的合作伙伴集合。综上所述,本文的研究深化了Petri网主干路径寻优理论,从而扩大了Petri网主干路径寻优的应用范围。借助本文人们可以全面且深入的了解Petri网主干路径寻找的研究理论与应用情况。
Since the Petri Net first be proposed by C.A.Petri in his doctoral dissertation in 1962, many researchers extend and improve this theory. People have done many researches about backbone of Petri Net since very earlier. The way which connects the input place and the output place and the total delay is shorter than any other ways is called backbone. It's the most efficient path in Petri Net, and it can determine capability of system in a way. A lot of problem in real life can be described as backbone's search of Petri Net. Transition has time delay in Petri Net; many researches described time delay as the impact factor, which affect the backbone's search of Petri Net. When the conditions are complicated, time delay can't describe the actual question. The article proposes a new Petri Net whose transition has reliability and reparability based on deeply research for backbone's search theory of Petri Net. We must consider not only the impact of time delay but also the impact of reliability and reparability when search for the backbone of Petri Net.
     This article will research on finding backbone of Petri Net with the clew that transition has reliability and reparability:
     This article analyzes the reliability of transition whose age obeys Weibull distribution. We build stochastic Petri Net model which has considered reliability and time delay. We combine Petri Net and Ant Colony Algorithm to search for backbone, the article also improves Ant Colony Algorithm in choice strategy, update odor elements and update place elements. Then, the article offers the algorithm of finding backbone, the result of instances proves that the Algorithm is correct.
     Un-repairable transition only has reliability; repairable transition not only has reliability but also has reparability. The usability, which synthetically considers the reliability and reparability, is another important factor affects backbone's search of Petri Net. The article offers another algorithm of finding backbone based on usability of transition. The algorithm improves Ant Colony Algorithm over again and proposes random search token. This Ant Colony algorithm, which considers usability, time delay and service cost, is used to find the backbone in Petri Net. Result of instances proves that the Algorithm can find the backbone.
     Distribution functions of reliability and reparability are diversity, they can obey exponential distribution both, and they also can obey different distribution. When reliability obeys Weibull distribution and reparability obey logarithmic normal distribution, it adjoins to real life the most. After get the computation method of usability, the article builds Petri Net model. Using some new methods to modify Ant Colony algorithm, such as choice strategy based on normal distribution, updates method of odor elements based on uniform distribution and odor balance factor, volatile factor modify odor and so on. At last the article uses the improved Ant Colony algorithm to find backbone. Result of instances proves that the Algorithm can find the backbone.
     After the article searches for backbone three times, the theory combines Ant Colony algorithm and Petri Net is proved completely correct. The article applies this theory on the question of partner's selection in supply chain network, instances proves that algorithm can find the best partners. After all, this article deepens the search theory of backbone's search in Petri Net and enlarges the coverage of backbone's search. People can completely and deeply acquire the research theory and application scenario of backbone's search in Petri Net by this article.
引文
[1]林闯.随机Petri网和系统性能评价(第二版)[M].北京:清华大学出版社,2005.
    [2]苏海洋.Petri网路径寻优[D].西安建筑科技大学硕士论文,2007.
    [3]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,2005.
    [4]黄圣国,孙同江,吕兵.运输网络的最短有向路Petri网仿真算法[J].南京:南京航空航天大学学报,2002,(2):121-125.
    [5]张威,黄圣国,麻士东.基于Petri网的交通运输网络最短路径算法[J].华北航天工业学院学报,2003,(12):16-19.
    [6]刘振峰,陈燕.基于时间petri网的供应链网络关键路径分析[J].教学的实践与认识,2006,(11):32-37.
    [7]吕光明,陆念力,夏堃.自动化仓库的Petri网建模和路径优化[J].起重运输机械,2004,(5):13-14.
    [8]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
    [9]杨瑞,张海英,潘永湘.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制,2004,04:241-244.
    [10]刘立东,蔡准,赵旭.一类自适应蚁群算法的收敛性分析[J].计算机应用,2007,06:73-75.
    [11]鬲钢力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制,2002,31(3):198-201
    [12]杨瑞,张海英,潘永湘.混合自.适应蚁群算法及其应用研究[J].西安理工大学学报,2005,21:405-408.
    [13]杨瑞臣,周永付,云庆夏.寻找车辆最优路径的混合算法[J].交通运输工程学报,2005,5(1):102-105
    [14]黄贵玲,高习全.基于蚁群算法的最短路径问题的研究和应用[J].计算机工程与应用,2007,43(13):233-235.
    [15]夏立民,王华,窦倩基于蚁群算法的最优路径选择问题的研究[J].计算机工程与设计,2007,28(16):3957-3959.
    [16]谢铎,周井泉.基于蚁群算法的QoS最佳路由选择问题的研究[J].计算机工程与应用,2007,43(3):112-118.
    [17]乐晓波,李京京,唐贤瑛.基于Petri net建模的资源调度的蚁群算法[J].计算机技术与发展 2006,(1):44.
    [18]邵志芳,刘重英,钱省三.整合petri网和蚁群优化算法用于柔性制造系统调 度优化研究[J].计算机应用,2006,(11):2753.
    [19]黄光球,苏海洋,刘冠.基于蚁群算法的Petri网最优路径序列寻找[J].计算机应用,2007,27(4):932-935.
    [20]苏海洋,黄光球.基于蚁群算法的随机Petri网最优路径序列寻找[J].系统仿真学报,2008,(12)(待印刷).
    [21]陈亚华,吴时霖.基于模糊有色Petri网的不确定性学习和推理方法[J],系统仿真学报(增刊),2003(8):56.
    [22]李洋,乐晓波.模糊Petri网与遗传算法相结合的优化策略[J].计算机应用,2006,26(1):187-189.
    [23]周卫东,杨加敏,贾磊等.一种Petfi网结合遗传算法的优化方法及应用[J],山东大学学报(工学版),2005,35(4):59-67.
    [24]Ahmed Tarek,Noe Lopez Benitez.Optimal Legal Firing Sequence of Petri Nets Using Linear Programming[J].Optimaization and Engineering.2004,5(3),25-43.
    [25]Lefebvre,Demitri;El Moudni,Abdellah.Firing and Enabling Sequences Estimation for Timed Petri Nets[J].IEEE Transactions on Systems,Man &Cybernetics:Part A,May2001,Vol.31 Issue 3,p153,10p,2 charts,6 diagrams,5graphs,2bw;(AN 4737674)153-162.
    [26]Dimitris Kiritsis,Michel Porchet.A generic Petri net model for dynamic process planning and sequence optimization Advances in Engineering Software,1996,25(1):61-71.
    [27]金伟娅,张康达.可靠性工程[M].北京:化学工业出版社,2005.
    [28]孙新利,陆长捷.工程可靠性教程[M].北京:国防工业出版社,2005.
    [29]赵涛,林青.可靠性工程基础[M].天津:天津大学出版社,1999.
    [30]金星,洪延姬.系统可靠性与可用性分析方法[M].北京:国防工业出版社,2007.
    [31]陈晓彤,赵延弟.可靠性使用指南[M].北京:北京航空航天大学出版社,2005.
    [31]孔德良,王少萍.可修系统的可用度分析方法研究[J].北京:北京航空航天大学学报,2002,28(2):129-132.
    [32]杨宇航,冯允成.复杂可修系统可靠性维修性综合仿真研究[J].系统仿真学报,2002,08:978-986.
    [33]邓立群,高连华,杨宏伟威布尔过程模型在机械系统可靠性中的应用[J].装甲兵工程学院学报,1999,(6):37-40.
    [34]王芙蓉,吴铁军.基于Petri网仿真的柔性生产调度—蚁群遗传递阶进化优化 方法[J].浙江大学学报(工学版),2004,(3):286-291.
    [35]孙靖,林杰.基于蚁群算法的大规模定制供应链调度优化研究[J].计算机应用,2006,(11):2631-2638.
    [36]马祖军,基于遗传算法的供应链联盟伙伴选择[J].系统工程理论与实践,2003,(9):81-84.
    [37]张悦,夏娜,张国富.基于免疫遗传的敏捷供应链伙伴选择[J],计算机工程与应用,2006,(21)203-206.
    [38]陆秋琴,黄光球,贾颖峰.供应链联盟成员最有选择的新方法[J].企业天地,2006,(1):139-140.
    [39]蒋仁言.威布尔模型族(特性,参数估计和应用)[M].北京:科学出版社,1998.
    [40]陈殿生,王田苗等.数控车床故障分布的两重威布尔分段模型[J].北京:北京航空航天学报,2005,31(7):766-769.
    [41]李士勇.蚁群算法及其原理[M].哈尔滨:哈尔滨工业大学出版社,2004.
    [42]李勇,段正澄.动态蚁群算法求解TSP问题[J].计算机工程与应用,2003,17:103-106.
    [43]黄永青,梁昌永,张详德.基于均匀设计的蚁群算法参数设计[J].控制与决策,2006,21(1):93-96.
    [44]叶小勇,雷勇,侯海军.蚁群算法在全局最优路径寻优中的应用[J].系统方针学报,2007,12:5643-5647.
    [45]曾欢彦.动态网络中最优路径问题的改进蚁群算法[D].暨南大学,2007.
    [46]程江,张广生.修理设备可修的单部件可修系统[J].西南民族大学报(自然科学版),2006,(9):870-873.
    [47]盛宇华,潘持春.供应链管理及虚拟产业链[M].北京:科学出版社,2004.
    [48]常良峰,王静,黄小原.供应链的成本模型及其优化*[J].系统工程,2002,(11):13-17.
    [49]彭禄斌,赵林度.供应链网状结构中多级库存控制模型[J].东南大学学报(自然科学版),2002,(3):217-222.
    [50]刘晓.基于供应链的供应商选择模型与算法[J].仪器仪表学报,2005,(8):890-892.
    [51]刘振峰,陈燕.基于时间petri网的供应链网络关键路径分析[J].教学的实践与认识,2006,(11):32-37.
    [52]罗新星.基于径向基网络的敏捷供应链伙伴选择实证研究[J].系统工程,2006,(8):13-18.
    [53]马士华.论核心企业对供应链战略伙伴关系形成的影响[J].工业工程与管理, 2000,(1)24-27.
    [54]李遂成,伊红英.基于Q学习的供应链分销系统最优订货策略研究[J].控制与决策,2005,(12):1404-1407.
    [55]周玲,供应链管理中的合作伙伴关系研究[J].兵工自动化,2002,(1):4-8.
    [56]Yang Y J,Jang S Y,Chang B M.etal.A combined model of network design and production distruction planning for a supply network[J].Computers & Industrial Enginneering,2002,43:263-289.
    [57]Xu kefeng,Dong Y,Evers P T.Towards better coordination of the supply[J].Transportation Research part E,2001,37:35-54.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700