【作者】 张斌；

【导师】 黄光球；

【作者基本信息】 西安建筑科技大学 ， 管理科学与工程， 2008， 硕士

【摘要】 自1962年C.A.Petri在博士论文中首先提出Petri网之后,人们就不断的对其进行理论延伸和改进。Petri网主干路径问题很早就受到人们的重视,主干路径是从输入库所到输出库所耗时最短的路径,它是贯穿系统的效率最高的路径,在一定程度上决定着系统的性能。现实生活中很多问题可以被模拟为Petri网主干路径的寻找问题。基本Petri网中变迁具有时间延迟的特性,以往的研究都是用时间延迟模拟影响主干路径的因素并寻找Petri网的主干路径。当情况复杂时,只能模拟单一因素的时间延迟特性并不能很好的模拟实际问题。本文经过对以往Petri网寻优理论的深入研究后提出一种变迁具有可靠性和可维修性的Petri网,影响Petri网主干路径寻找的因素不仅包括时间延迟,还有变迁的可靠性和维修性。本文围绕变迁具有可靠性和维修性这一主线对Petri网的主干路径寻找问题进行深入研究:文中首先分析了寿命服从威布尔分布的变迁的可靠性变化情况,在考虑可靠性和时间延迟的因素后建立随机Petri网模型,并用蚁群算法与Petri网结合的方法寻找主干路径,同时在选路策略、信息素更新、库所更新等问题上对蚁群算法进行改进,然后以数学形式提出变迁具有可靠性的Petri网主干路径寻优算法,实例证明了算法的正确性。不可维修的变迁仅仅具有可靠性,但是可维修的变迁不仅具有可靠性还具有维修性,综合考虑了可靠性与维修性的可用度是影响主干路径寻找的另一重要因素,本文随后又提出变迁具有可用度的Petri网主干路径寻优算法,该算法重新改进了蚁群算法并引入随机搜索托肯。在考虑了可用度、时间延迟和维修成本等多个影响因素后的蚁群算法在Petri网中进行路径寻找,实例证明算法能够找到主干路径。可靠性和维修性的分布函数是多样的,可以同时都服从指数分布,也可能服从不同的分布,可靠性服从威布尔分布且维修性服从对数正态分布的情况最贴近实际问题。在分析了可用度的计算方法之后,本文继而建立相应的Petri网模型,并用基于正态分布的路径选择算法、基于均匀分布信息量均衡算子的路径信息素更新策略和修改信息素的挥发因子等新方法对蚁群算法进行再改进,最后利用改进的蚁群算法来寻找到主干路径,实例证明算法能够解决实际问题。经过三次使用,蚁群算法与Petri网结合的理论已被证明是完全正确的,随后本文将这一理论应用到供应链网络的合作伙伴选择问题上,应用该方法在供应链网络模型中进行主干路径寻找,实例证明算法可以选择到最优的合作伙伴集合。综上所述,本文的研究深化了Petri网主干路径寻优理论,从而扩大了Petri网主干路径寻优的应用范围。借助本文人们可以全面且深入的了解Petri网主干路径寻找的研究理论与应用情况。更多还原

【Abstract】 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.更多还原