Dynamic analysis of repetitive decision-free discreteevent processes: The algebra of timed marked graphs and algorithmic issues

A model to analyze certain classes of discrete event dynamic systems is presented. Previous research on timed marked graphs is reviewed and extended. This model is useful to analyze asynchronous and repetitive production processes. In particular, applications to certain classes of flexible manufacturing systems are provided in a companion paper. Here, an algebraic representation of timed marked graphs in terms of reccurrence equations is provided. These equations are linear in a nonconventional algebra, that is described. Also, an algorithm to properly characterize the periodic behavior of repetitive production processes is descrbed. This model extends the concepts from PERT/CPM analysis to repetitive production processes.     

Modelling and hierarchical diagnosis of timed discrete-event systems

A new diagnostic method for hierarchically structured discrete-event systems is presented. The efficiency of this method results from the fact that the complexity of the diagnostic task is reduced by first detecting a faulty component using a coarse process model on a high level of abstraction, and subsequently refining the result by investigating the faulty component with the help of a detailed component model in order to identify the fault with sufficient precision. On both abstraction levels, the method uses a timed discrete-event model of the appropriate part of the system. On the higher abstraction level a timed event graph is used that describes how the temporal distance of the events is changed by component faults. On the lower level of abstraction, timed automata are used to cope with the non-determinism of the event sequence generated by the faulty and faultless components. The approach is illustrated by the diagnosis of a batch process.     

An extended event graph-based modelling method for parallel and distributed discrete-event simulation

The developing logical process (LP)-based parallel and distributed discrete-event simulation (PDES) in the existing PDES programming environments is a difficult and time-consuming process. Event graph is a simple and powerful modelling formalism of discrete-event simulation, whereas this formalism does not support PDES. This article proposes an extension of the event graph to consider the communication of LPs via the events sent, which is called ‘extended event graph (EEG)’, and proposes an EEG-based modelling method for PDES. This modelling method shifts the focus of PDES development from writing code to building models, and the system implementation can be automatically and directly generated from EEG model. The experimental results show that EEG models can successfully execute in the parallel simulator, and this framework can effectively improve the PDES modelling activities.     

非零势能的耗散力学控制系统的位形能控性

在拉格朗日力学控制系统的仿射联络框架下,基于Sussmann对有限维流形上一般仿射非线性控制系统的能控性讨论,将简单力学控制系统短时间局部位形能控的一个可计算的充分条件推广到迷向耗散的系统上,并给出系统是平衡点能控的一个充分条件,其中,系统的拉格朗日函数为动能减势能A·D2在问题的讨论中,系统的能控李代数的向量场李括号运算,以及与系统位形流形的Levi-Civita联络相关的对称积起了重要作用．尽管势能项会使系统的位形能控性讨论复杂化,但Liouville向量场又简化了系统的能控李代数计算．     

A sufficient condition for the liveness of weighted event graphs

Weighted event graphs (in short WEG) are widely used to model industrial problems and embedded systems. In an optimization context, fast algorithms checking the liveness of a marked WEG must be developed. The purpose of this paper is to develop a sufficient condition of liveness of a WEG. We first show that any unitary WEG can be transformed into a graph in which the values of the arcs adjacent to any transition depend on the transition. Then, a simple sufficient condition of liveness can be expressed on this new graph and polynomially computed. This condition is shown to be necessary for a circuit with two transitions.     

Tails for (max, plus) recursions under subexponentiality

We study the stationary solution of a (max, plus)-linear recursion. Under subexponentiality assumptions on the input to the recursion, we obtain the tail asymptotics of certain (max, plus)-linear functionals of this solution. (Max, plus)-linear recursions arise from FIFO queueing networks; more specifically, from stochastic event graphs. In the event graph setting, two special cases of our results are of particular interest and have already been investigated in the literature. First, the functional may correspond to the end-to-end sojourn time of a customer. Second, for two queues in tandem, the functional may correspond to the sojourn time in the second queue. Our results allow for more general networks, which we illustrate by studying the tail asymptotics of the resequencing delay due to multi-path routing.     

An upper bound on the cycle time of a stochastic marked graph using incomplete information on the transition firing time distributions

Stochastic marked graphs, a special class of stochastic timed Petri nets, are used for modelling and analyzing decision-free dynamic systems with uncertainties in timing. The model allows evaluating the performance of such systems under a cyclic process. Given the probabilistic characteristics of the transition times, the cycle time of the system can be determined from the initial marking. In this contribution, we compute an upper bound on the cycle time of a stochastic marked graph in case the probabilistic characteristics of the transition times are not fully specified.     

Modeling Discrete Event Systems With Faults Using a Rules-based Modeling Formalism

Obtaining accurate models of systems which are prone to failures and breakdowns is a difficult task. In this paper we present a methodology which makes the task of modeling failure prone discrete event systems (DESs) considerably less cumbersome, less error prone, and more user-friendly. The task of obtaining commonly used automata models for DESs is non-trivial for most practical systems, owing to the fact that the number of states in the commonly used automata models is exponential in the number of signals and faults. In contrast a model of a discrete event system, in the rules based modeling formalism proposed by the co-authors of this paper, is of size polynomial in the number of signals and faults. In order to model failures, we augment the signals set of the rules based formalism to include binary valued fault signals, the values representing either a non-faulty or a faulty state of a certain failure type. Addition of new fault signals requires introduction of new rules for the added fault signal events, and also modification of the existing rules for non-fault events. The rules based modeling formalism is further extended to model real-time systems, and we apply it to model delay-faults of the system as well. The model of a failure prone DES in the rules based can automatically be converted into an equivalent (timed)-automaton model for a failure analysis in the automaton model framework.     

Relational Galois connections between transitive fuzzy digraphs

Fuzzy-directed graphs are often chosen as the data structure to model and implement solutions to several problems in the applied sciences. Galois connections have also shown to be useful both in theoretical and in practical problems. In this paper, the notion of relational Galois connection is extended to be applied between transitive fuzzy directed graphs. In this framework, the components of the connection are crisp relations satisfying certain reasonable properties given in terms of the so-called full powering.     

Convergence properties of ordinal comparison in the simulation of discrete event dynamic systems

Recent research has demonstrated that ordinal comparison has fast convergence despite the possible presence of large estimation noise in the design of discrete event dynamic systems. In this paper, we address the fundamental problem of characterizing the convergence of ordinal comparison. To achieve this goal, an indicator process is formulated and its properties are examined. For several performance measures frequently used in simulation, the rate of convergence for the indicator process is proven to be exponential for regenerative simulations. Therefore, the fast convergence of ordinal comparison is supported and explained in a rigorous framework. Many performance measures of averaging type have asymptotic normal distributions. The results of this paper show that ordinal comparison converges monotonically in the case of averaging normal random variables. Such monotonicity is useful in simulation planning.The author would like to thank C. G. Cassandras, X. Chao, S. G. Strickland, X. Xie, and the reviewers for their helpful suggestions.     

Decidability and complexity of event detection problems for ODEs

The ability of ordinary differential equations (ODEs) to simulate discrete machines with a universal computing power indicates a new source of difficulties for event detection problems. Indeed, nearly any kind of event detection is algorithmically undecidable for infinite or finite half-open time intervals, and explicitly given “well-behaved” ODEs (see [18]). Practical event detection, however, usually takes place on finite closed time intervals. In this article, the undecidability of general event detection is extended to such intervals. On the other hand, on finite closed time intervals, event detection in a certain approximate sense is quite generally decidable, which partly saves the case for practicable event detection. The capability of simulating universal Turing machines is still there, and is used to give complexity lower bounds in terms of accuracy of event detection. The ODEs used here are, of course, quite complicated, but not artificial, in that even from the point of view of practical event detection, it would appear difficult to find criteria to exclude them. © 1997 John Wiley & Sons, Inc.     

基于行为分析的AS/RS有色赋时Petri网模型研究

为了研究如何提高AS/RS系统的性能,有必要构建其模型.提出了库所双重着色的有色赋时Petri网方法,分析了AS/RS系统活动资源的行为特点和要求,并详细阐述了使用有色赋时Petri网分别构建这些行为模型的过程,从而实现整个AS/RS系统框架模型.采用visual c++软件仿真表明,该方法在构建面向资源的离散系统模型时是有效的.     

On the L<Subscript>∞</Subscript>-norm of extreme points for crossing supermodular directed network LPs

We discuss extensions of Jain’s framework for network design [8] that go beyond undirected graphs. The main problem is approximating a minimum cost set of directed edges that covers a crossing supermodular function. We show that iterated rounding gives a factor 3 approximation, where factor 4 was previously known and factor 2 was conjectured. Our bound is tight for the simplest interpretation of iterated rounding. We also show that (the simplest version of) iterated rounding has unbounded approximation ratio when the problem is extended to mixed graphs.      

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.     

Modelling routing phenomenon with bounds estimation in dioids

In job-shop systems, each product is routed according to its own production cycle. However routings or conflicts cannot be modelled in scalar dioid algebraic structures such as or (also denoted and ). The main reason is that choices cannot be represented in such modellings. In this article the input/output behaviour of a whole system with several sub-systems in conflict is bounded by those of two linear systems in dioid . By doing so, we model behaviours as intervals. An interval contains all the possible system behaviours (in terms of number of pallets coming and going, delays and production rates), when the routing policy therein is periodic. As a consequence, even though the input/output behaviour of such a system is not linear in a scalar dioid, we can nevertheless use an imprecise modelling over a dioid of intervals. This allows for using dioid theory contributions, as for control problem synthesis issues.     

Crossing minimization in extended level drawings of graphs

The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles.In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings.We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.     

Dynamic graph generation for the shortest path problem in time expanded networks

In discrete optimization problems the progress of objects over time is frequently modeled by shortest path problems in time expanded networks, but longer time spans or finer time discretizations quickly lead to problem sizes that are intractable in practice. In convex relaxations the arising shortest paths often lie in a narrow corridor inside these networks. Motivated by this observation, we develop a general dynamic graph generation framework in order to control the networks’ sizes even for infinite time horizons. It can be applied whenever objects need to be routed through a traffic or production network with coupling capacity constraints and with a preference for early paths. Without sacrificing any information compared to the full model, it includes a few additional time steps on top of the latest arcs currently in use. This “frontier” of the graphs can be extended automatically as required by solution processes such as column generation or Lagrangian relaxation. The corresponding algorithm is efficiently implementable and linear in the arcs of the non-time-expanded network with a factor depending on the basic time offsets of these arcs. We give some bounds on the required additional size in important special cases and illustrate the benefits of this technique on real world instances of a large scale train timetabling problem.     

A unifying framework for teaching probability event types

The concepts and mathematics of mutually exclusive, dependent and independent events are developed in a unifying framework of event association.     

Analysis of stochastic min-max-plus systems: Results and conjectures

Systems in which the operations min, max and addition appear simultaneously are called min-max-plus systems. Such systems, which are extensions of timed discrete event systems (which on their turn are based on the max-plus algebra, i.e., on the operations max and addition only), have been studied for some years now [1–3]. In these references only deterministic systems were studied. In the current paper, some stochastic extensions will be considered. It will be shown that extensions of eigenvalues, Lyapunov coefficients, exist for these stochastic systems. Some conjectures will be given which are supported by characteristic examples.