A discrete event system is a dynamical system whose state evolves in time by the occurrence of events at possibly irregular time intervals. Timed Petri nets are a graphical and mathematical modeling tool applicable to...A discrete event system is a dynamical system whose state evolves in time by the occurrence of events at possibly irregular time intervals. Timed Petri nets are a graphical and mathematical modeling tool applicable to discrete event systems in order to represent its states evolution where the timing at which the state changes is taken into consideration. One of the most important performance issues to be considered in a discrete event system is its stability. Lyapunov theory provides the required tools needed to aboard the stability and stabilization problems for discrete event systems modeled with timed Petri nets whose mathematical model is given in terms of difference equations. By proving stability one guarantees a bound on the discrete event systems state dynamics. When the system is unstable, a sufficient condition to stabilize the system is given. It is shown that it is possible to restrict the discrete event systems state space in such a way that boundedness is achieved. However, the restriction is not numerically precisely known. This inconvenience is overcome by considering a specific recurrence equation, in the max-plus algebra, which is assigned to the timed Petri net graphical model.展开更多
In this paper, stochastic stabilization is investigated by max-plus algebra for a Markovian jump cloud control system with a reference signal. For the Markovian jump cloud control system, there exists framework adjust...In this paper, stochastic stabilization is investigated by max-plus algebra for a Markovian jump cloud control system with a reference signal. For the Markovian jump cloud control system, there exists framework adjustment whose evolution is satisfied with a Markov chain. Using max-plus algebra, a maxplus stochastic system is used to describe the Markovian jump cloud control system. A causal feedback matrix is obtained by exponential stability analysis for a causal feedback controller of the Markovian jump cloud control system. A sufficient condition is given to ensure existence on the causal feedback matrix of the causal feedback controller. Based on the causal feedback controller, stochastic stabilization in probability is analyzed for the Markovian jump cloud control system with a reference signal.Simulation results are given to show effectiveness of the causal feedback controller for the Markovian jump cloud control system.展开更多
This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in whi...This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.展开更多
Max-plus algebra has been widely used in the study of discrete-event dynamic systems.Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of...Max-plus algebra has been widely used in the study of discrete-event dynamic systems.Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of state variables,i.e.,firing times of relevant events.This paper proves that the problem of solving max-plus inequalities in a cube(MAXINEQ)is nondeterministic polynomial-time hard(NP-hard)in strong sense and the problem of verifying max-plus inequalities(VERMAXINEQ)is co-NP.As a corollary,the problem of solving a system of multivariate max-algebraic polynomial equalities and inequalities(MPEI)is shown to be NP-hard in strong sense.The results indicate the difficulties in comparing max-plus formulas in general.Problem structures of specific systems have to be explored to enable the development of efficient algorithms.展开更多
High-speed rail(HSR) has formed a networked operational scale in China. Any internal or external disturbance may deviate trains’ operation from the planned schedules, resulting in primary delays or even cascading del...High-speed rail(HSR) has formed a networked operational scale in China. Any internal or external disturbance may deviate trains’ operation from the planned schedules, resulting in primary delays or even cascading delays on a network scale. Studying the delay propagation mechanism could help to improve the timetable resilience in the planning stage and realize cooperative rescheduling for dispatchers. To quickly and effectively predict the spatial-temporal range of cascading delays, this paper proposes a max-plus algebra based delay propagation model considering trains’ operation strategy and the systems’ constraints. A double-layer network based breadth-first search algorithm based on the constraint network and the timetable network is further proposed to solve the delay propagation process for different kinds of emergencies. The proposed model could deal with the delay propagation problem when emergencies occur in sections or stations and is suitable for static emergencies and dynamic emergencies. Case studies show that the proposed algorithm can significantly improve the computational efficiency of the large-scale HSR network. Moreover, the real operational data of China HSR is adopted to verify the proposed model, and the results show that the cascading delays can be timely and accurately inferred, and the delay propagation characteristics under three kinds of emergencies are unfolded.展开更多
文摘A discrete event system is a dynamical system whose state evolves in time by the occurrence of events at possibly irregular time intervals. Timed Petri nets are a graphical and mathematical modeling tool applicable to discrete event systems in order to represent its states evolution where the timing at which the state changes is taken into consideration. One of the most important performance issues to be considered in a discrete event system is its stability. Lyapunov theory provides the required tools needed to aboard the stability and stabilization problems for discrete event systems modeled with timed Petri nets whose mathematical model is given in terms of difference equations. By proving stability one guarantees a bound on the discrete event systems state dynamics. When the system is unstable, a sufficient condition to stabilize the system is given. It is shown that it is possible to restrict the discrete event systems state space in such a way that boundedness is achieved. However, the restriction is not numerically precisely known. This inconvenience is overcome by considering a specific recurrence equation, in the max-plus algebra, which is assigned to the timed Petri net graphical model.
基金supported by the National Natural Science Foundation of China (61973230)Tianjin Research Innovation Project for Postgraduate Students (2021YJSO2S03)。
文摘In this paper, stochastic stabilization is investigated by max-plus algebra for a Markovian jump cloud control system with a reference signal. For the Markovian jump cloud control system, there exists framework adjustment whose evolution is satisfied with a Markov chain. Using max-plus algebra, a maxplus stochastic system is used to describe the Markovian jump cloud control system. A causal feedback matrix is obtained by exponential stability analysis for a causal feedback controller of the Markovian jump cloud control system. A sufficient condition is given to ensure existence on the causal feedback matrix of the causal feedback controller. Based on the causal feedback controller, stochastic stabilization in probability is analyzed for the Markovian jump cloud control system with a reference signal.Simulation results are given to show effectiveness of the causal feedback controller for the Markovian jump cloud control system.
文摘This research develops a solution method for project scheduling represented by a max-plus-linear (MPL) form. Max-plus-linear representation is an approach to model and analyze a class of discrete-event systems, in which the behavior of a target system is represented by linear equations in max-plus algebra. Several types of MPL equations can be reduced to a constraint satisfaction problem (CSP) for mixed integer programming. The resulting formulation is flexible and easy-to-use for project scheduling;for example, we can obtain the earliest output times, latest task-starting times, and latest input times using an MPL form. We also develop a key method for identifying critical tasks under the framework of CSP. The developed methods are validated through a numerical example.
基金supported by the National Natural Science Foundation of China (Grant Nos.60574067 and 60721003).
文摘Max-plus algebra has been widely used in the study of discrete-event dynamic systems.Using max-plus algebra makes it easy to specify safety constraints on events since they can be described as a set of inequalities of state variables,i.e.,firing times of relevant events.This paper proves that the problem of solving max-plus inequalities in a cube(MAXINEQ)is nondeterministic polynomial-time hard(NP-hard)in strong sense and the problem of verifying max-plus inequalities(VERMAXINEQ)is co-NP.As a corollary,the problem of solving a system of multivariate max-algebraic polynomial equalities and inequalities(MPEI)is shown to be NP-hard in strong sense.The results indicate the difficulties in comparing max-plus formulas in general.Problem structures of specific systems have to be explored to enable the development of efficient algorithms.
基金supported by the National Natural Science Foundation of China (U1834211, 61925302, 62103033)the Open Research Fund of the State Key Laboratory for Management and Control of Complex Systems (20210104)。
文摘High-speed rail(HSR) has formed a networked operational scale in China. Any internal or external disturbance may deviate trains’ operation from the planned schedules, resulting in primary delays or even cascading delays on a network scale. Studying the delay propagation mechanism could help to improve the timetable resilience in the planning stage and realize cooperative rescheduling for dispatchers. To quickly and effectively predict the spatial-temporal range of cascading delays, this paper proposes a max-plus algebra based delay propagation model considering trains’ operation strategy and the systems’ constraints. A double-layer network based breadth-first search algorithm based on the constraint network and the timetable network is further proposed to solve the delay propagation process for different kinds of emergencies. The proposed model could deal with the delay propagation problem when emergencies occur in sections or stations and is suitable for static emergencies and dynamic emergencies. Case studies show that the proposed algorithm can significantly improve the computational efficiency of the large-scale HSR network. Moreover, the real operational data of China HSR is adopted to verify the proposed model, and the results show that the cascading delays can be timely and accurately inferred, and the delay propagation characteristics under three kinds of emergencies are unfolded.
