The Shortcuts And Periodicity Of The Networked Max-plus System With Ring Topology

Control science researchers conducts a depth research for the networked system dynamicand obtains many important results. For nodes with a logic state, through the event triggermechanism driven system evolution of the networked discrete event dynamic system, due tothe change of state of discontinuous, concurrent, asynchronous and uncertain characteristics,relative to the differential equation or difference equations describing networked continuoustime dynamic system, the modeling and analysis methods in both the forms of conciseness andthere is a big difference in calculation. For the networked discrete event dynamic systems, theresearchers used max-plus system modeling and analysis. The study of the networked max-plussystem is unfolding.In2011, Zhao Q. studied the changes of timing performance after adding shortcuts tothe networked max-plus dynamic systems with ring topology. The lower bound expressionof the probability of cyclicity being1is given after adding one, two and three shortcuts, aswell as the condition for the cycle time unchanged are established after adding one shortcuts.In2012, Addad B, Amari S and Lesage J J studied the networked event graph and gave themax-plus algebra representation of the time-invariant with the class network time event graph,and analyzed the performance of the network time event graph, and van den Boom T J J andDe Schutter B researched the switching of different operation modes with the switching max-plus system and indicated that using the linear programming algorithm to solve optimizationproblems, meanwhile, discussed the two equivalent description of the system and demonstratedthe switching max-plus system can be represed to the segment affine systems.This thesis investigates the lower bound of the probability of cyclicity being1and the cycletime unchanged after adding shortcuts to the networked max-plus system with ring topology.The full text is divided into seven parts.In the first part, we describe some research background and current status of the max-plussystem.In the second part, we give some basic concepts and properties, such as the max-plussystem, the cycle time and cyclicity.In the third part, the lower bound expression of the probability of cyclicity being1is givenafter adding k shortcuts with the same starting point, and the detailed proof is also given, Fortwo systems with dimensions of prime number and its power, it is found out that the lowerbounds of the probability of cyclicity being1is consistent after adding shortcuts with the same starting point.The expression of cycle time is given and examined in the fourth part, the sufficient andnecessary condition for the cycle time unchanged are established. The method of algebra andcombinatorics is constructive.The algorithm of the cycle time remain unchanged is given after adding k shortcuts withthe same starting point. It is proved that the algorithm is polynomial algorithm, at the same timethe numerical examples are also given in the fifth part. The description of the two deductions isalso clearerly given by the numerical example in the third part.The sixth part investigates some situations of adding shortcuts under the condition withthe different starting points. It is analysed that the lower bound expression of the probabilityof cyclicity being1and the sufficient and necessary condition for the cycle time unchangedare established after adding two and three shortcuts with the different starting point. The lowerbound expression of the probability of cyclicity being1and the number of the new loops aregiven after adding k shortcuts of mutually disjoint with the different starting points, the detailedproof is also given.The final part of this paper summarizes the main conclusion of this article and puts forwardsome problems to be studied in the future.