This thesis presents deterministic timing constraint Petri nets with weak firing rules (WDTCPN) and their use in qualitative and quantitative analysis and schedules of discrete event systems. It is organized as follows. Chapter 1 discusses the background and motivation of this research. Chapter 2 reviews timing constraint Petri nets and structural analysis of Petri net(PN). Chapter 3 introduces the basic notation of PN ,in addition analyzes the relation between four kinds of DTCPNs and their underlying nets, and points out some problems and the reason why these problems occur when these DTCPN are used in qualitative analysis and performance evaluation of DES. Thus we present and discuss four kinds of WDTCPNs. In parallel to PN, chapter 4 defines a series of concepts for timed PNs with weak firing rules(WTPN), gives generative approaches for state reachable graph and state coverable graph, and proves that WTPN is equivalent to its underlying net about liveness, boundedness and reversibility. Thus the formally descriptive and analytical framework for WTPN is established. In chapter 5,scheduling theory of WTPN is studied. Initial Markings which makes a finite controlled execution realizable are proved being presence and form a lattice,and the recursive formula for computing the minimal Marking is given. The sufficient (necessary) condition for a complete and periodic controlled execution realizable(and bounded) is presented. It is proved that one firable transition(subset) sequence corresponds to infinite schedules and the earliest one has the shortest execution time. Three kinds of periodic schedules are discussed. Schedules with deadlines and latest schedules are defined. The sufficient and necessary condition for existence and two approches forconstruction of the latest schedule corresponding to a finite firable transition (subset) sequence is presented, and the existence and computation of the latest schedule corresponding to a infinite firable transition (subset) sequence for timed event graphs(TEG) is discussed by means of extended firing graph. In chapter 6,periodic schedule Ⅱ is transformed into periodic schedule I by means of a group of rules, the sufficient and necessary condition for the latter realizable is given, and the recursively computing method and heuristic algorithm for the latter's optimiztion are presented. The close formula for computing minimal cycle time of weighted and timed event graph(WTEG) under infinite--server semantics and the formula for computing the optimistic and pessimistic bounds of minimal cycle time for WTEG under single--server semantics are derived.
修改评论