Optimal Path Research Based On Timed Petri Nets

Given a fixed firing time to each transition of a Petri net,a timed Petri net can be obtained.Timed Petri nets hava stronger system modeling and analysis capabilities,such as calculating the production cycle,optimal path planning,etc.In a timed Petri net,the path which takes the least time from the initial marking to the reference one is called the optimal path.The optimal path determines the production efficiency of a system to a large extent in a timed Petri net,therefore it is of great significance to calculate the optimal path of timed Petri nets.Timed Petri nets have the characteristics of sequence,parallel,branch,loop,conflict and other structural features,in particular time factor should also be taken into consideration.Therefore seeking the optimal path in a timed Petri net is more complicated.The basic idea of seeking the optimal path and main work of this thesis is as follows.Firstly,from the incidence matrix and state equation of a timed Petri net,a transition firing vector is obtained by solving state equation.If the state equation has no solution,it means that the reference marking is unreachable.Secondly,the transition firing times can be are determined in combination with the minimum time constraint.According to the firing times of transition,control places are added to the corresponding transitions and then a new timed Petri net is obtained.Finally,the reachability graph of the timed Petri net is calculated,and the transition firing sequence is obtained by using Dijkstra algorithm.Considering that the state equation is a necessary but not sufficient condition for the state reachability,there is a necessity to prove the authenticity of the firing sequence.Estimating the existence of a firing sequence is to analyse whether each transition of a firing sequence is enabled in the actual model,and whether it can reach the specified reference marking from the initial one.It means the firing sequence is legal if reference marking can arrive,otherwise it is illegal.The paper presents an algorithm to testify the existence of a firing sequence.The optimal path from the initial marking to the reference one is studied under the framework of a timed Petri net.The proposed method in the thesis adds a control place to the corresponding transition according to the transition firing vector.It limits the firing times of the corresponding transition and avoids calculating the whole state space of a timed Petri net.And it can ensure the shortest time of the transition firing sequence calculated.The algorithm proposed in this paper still has some shortcomings,mainly in three aspects.Firstly,the algorithm presented in this paper is applicable only when the reference marking is reachable.For the case that the equation of state has a solution but the reference marking is not reachable,further study is needed.Secondly,the algorithm proposed in this paper uses Dijkstra algorithm to solve the problem.For large-scale nets,it can not get the desired results.Thirdly,this paper studies the case of non-concurrent transitions.The situation of concurrent transitions needs further study.The next work of this paper needs to further study the reachability of a marking,and avoid using Dijkstra algorithm to solve all paths,and the reachability graph of concurrent transitions.