Methodological Approach

The methodological approach will be centered around the following two main streams which can be distinguished within the theory of DESs:

• The `logical' approach, based on automata and formal languages, in which only the precise ordering of the events is of interest; this ordering must satisfy a given set of specifications imposed on it. Time does not play an explicit role. Representative references are [20], [21], [19] and [25]. The theory addresses the synthesis of controllers (`supervisors') for DES in order to satisfy a set of (qualitative) specifications on the admissible orderings of the events that can be executed by the system.
• The `timed' or max-plus algebra approach, in which, in addition to the ordering, the timing of the events plays an essential role. The starting point is a `linear' model, linear in the sense of the so-called max-plus algebra. Representative references are [9] and [1]. Nowadays a discrete event system theory exists, which parallels the classical linear system theory in several ways. The relationship with (timed) Petri nets and stochastic extensions is well understood.

In these two streams the theory of algebraic structures is dominantly present and one discovers more and more interrelationships, see [16], [8]. The concept of `Idempotency' is crucial in this respect.

Objectives and Tasks

The project has three objectives; 1. cross fertilisation on the theoretical level, 2. applications and 3. software. They are described in the following subsections in more detail. For the various tasks, the partners involved are given in parentheses, the first one mentioned being the first responsible.

Cross Fertilisation on the Theoretical Level

The primary objective of the project is to bring together the most active European groups working on the algebraic approach to the (temporal) analysis of discrete event systems, in order to deepen their mutual understanding and to cross fertilize the techniques which they currently develop. This objective was already initiated via the Bristol workshop held by BRIMS at the Hewlett-Packard Laboratories in Bristol, October 1994. Theory development will (partly) be guided by stimuli and questions from the applications side and the possibilities for software implementations. Currently we see good possibilities to understand better, to do research and obtain new results in:

T-1

Representation problems (TUD,KUL,ULG,RUG). What is the most convenient `state space representation' of a DES, given a specific problem? What is the minimal state representation of such systems within a given algebraic frame; these questions are important for several problems and particularly simulation, [1,15,14,23,24].

T-2

Stability problems (INRIA,ARMINES,TUD,ULG,HP). Under what conditions does a timed (resp. stochastic) discrete event system reach a periodic (resp. stationary) regime? These are already well understood in the [tex2html_wrap_inline127] case [1,18,2,3]. Stability issues for related, but more general systems such as those described by (subclasses of) Petri nets and nonexpansive mappings, are open and interesting problems for which the algebraic approach seems to be particularly well suited. Related to implementation issues, computational complexity of some of these problems will be investigated [4], [18].

T-3

Optimisation problems (INRIA,ARMINES). They cover general modelling of scheduling and control problems in discrete event systems [11] and more specific issues like register utilisation in computational circuits [15] and resource optimisation in production lines [13].

T-4

Control of automata (LIAFA,ULG,RUG). The combination of the automata aspects like in supervisory control and the maintenance of the linear structure of timed event graphs and/or Petri nets. Fundamental problems with respect to decidability and finiteness conditions will be addressed, [21], [26]. In line with recent work on non-associative structures [5], [12] formal series on binary trees for modelling purposes will be investigated.

T-5

Large systems problems (ARMINES). Investigation of the asymptotic properties of Discrete Event Systems when their size increases to infinity. There exist some bridges with mechanical statistics and interacting particle systems which could provide new techniques and results, [17,10]. We will also investigate relations with Hamilton-Jacobi-Bellman partial differential equations.

Applications

The second objective is to concentrate on a few key application areas where we will demonstrate the industrial relevance of this new algebraic approach. This will be based on the extension of ongoing industrial contacts of some of the proposers, and on the partnership of BRIMS(HP).

A-1

Transportation systems (optimisation of railway scheduling) (TUD, ARMINES, KUL). The relation between railway connections and time tables is quite successfully described by means of the max-plus algebra in [6,7]. We would like to extend this analysis on the intercity railway network in the Netherlands to larger systems.

A-2

Manufacturing systems (resource optimisation in production line) (ARMINES, INRIA). In the field of manufacturing systems, we are interested in performance evaluation and resource optimisation of flexible workshops, for example in mechanical engineering. Once the design and the performance of resources (machines, storage capacities, human resources), and scheduling policies (routing, priorities) are fixed, the problem of performance evaluation reduces to that of a synchronized system modelled as a Timed Event Graph (TEG) for which a good deal of theory is already available.

A-3

Communication networks (LIAFA, INRIA, HP, RUG). Important automata, control and identification problems in communication networks as well as timing analysis of digital circuits can also be approached within this algebraic framework. A reference is [7].

Software

The third objective is the elaboration of software tools built on the results obtained by the proposers. Such a set of tools is expected to contribute to the diffusion of the proposed techniques in industry.

S-1

Investigation and critical analysis of existing software (ARMINES,LIAFA). Currently we know of two software packages available in the European Union for handling finite automata and finite semigroups; they run in academic environments. The first one, developed under the supervision of J.-E. Pin (LIAFA) is a Pascal-oriented language that . activates two packages : AUTOMATE and MONOIDE.

The second package, AMORE, was developed under the supervision of W. Thomas (Kiel). It shares some of the features of AUTOMATE and MONOIDE, but has a specific module to treat star-free expressions.

Within the max-plus algebra context, a package based on MAPLE (symbolic computation system from Waterloo University), called MAX, implements linear algebraic calculus in the max-plus algebra with polynomial and power series manipulations. It can handle Timed Event Graphs (TEG). Some routines are also available for optimal sizing of resources using purely symbolic computation (for small systems) or appealing to external numerical routines. Parallel simulators based on the max-plus algebra representation of stochastic Event Graphs (SEG) were also developed at INRIA, on a Connection Machine and on a network of workstations.

S-2

Development of new software (ARMINES, LIAFA, INRIA, RUG, UGL). Both for theoretical and experimental reasons, there is a strong need for software tools to manipulate other mathematical objects. Our goal would be to add to these existing modules new features to handle in particular formal power series in non commutative variables and automata with outputs. These new modules should be written in C or C++.

Furthermore, the implementation of new algorithms in MAX (based on new internal object representation) will yield much better performance, probably by one order of magnitude in terms of computational time. The development of another package based on purely numerical computation (equivalent to MATLAB for max-plus and similar algebras) is also seen as important; this package would be hosted by SCILAB (a freeware MATLAB developed at INRIA) and would benefit from this environment. Bridges already exist between MAPLE and SCILAB and a similar integration would be available between all the planned software tools.

References

See also the pages of Stephane Gaubert and Jean-Pierre Quadrat for lists of publications.

1

F. Baccelli, G. Cohen, G.J. Olsder, and J.P. Quadrat. Synchronization and Linearity. Wiley, 1992.

2

F. Baccelli, S. Foss, and B. Gaujal. Structural, timed and stochastic properties of unbounded free choice petri nets. Rapport de recherche 2411, INRIA, 1994.

3

F. Baccelli and J. Mairesse. Ergodic theory of stochastic discrete event systems. In Idempotency. Cambridge Univ. Press, 1995.

4

V. Blondel and J. Tsitsiklis. NP-hardness of some linear control problems. Technical Report TRITA/MAT-94-33, Royal Institute of Technology - Stockholm (submitted SIAM J. Cont. Opt.), 1994.

5

V. Blondel. Operations on binary trees. C.R. Acad. Sci., to appear, 1995.

6

J.G. Braker. Algorithms and applications in timed discrete event systems. PhD thesis, Delft university of Technology, 1993.

7

C.G. Cassandras, S. Lafortune, and G.J. Olsder. Introduction to the modelling, control and optimization of discrete event systems. In A. Isidori, editor, European Control Conference, 75 pages. Springer Verlag, 1995.

8

D.D. Cofer and V.K. Garg. Supervisory Control of Real-Time Discrete-Event Systems Using Lattice Theory. IEEE Transactions on Automatic Control, volume 41, 1996, pp. 199-209.

9

R.A. Cuninghame-Green. Minimax Algebra. Number 166 in Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, Berlin, 1979.

10

B. Derrida, M. Evans, V. Hakim, and V. Pasquier. A matrix method of solving an asymmetric exclusion model with open boundaries. In Proceedings of Les Houches Workshop, Cellular Automata and Cooperative Systems, June 1992.

11

S. Gaubert and J. Mairesse. Task resource models, scheduling and (max,+) automata. 1995.

12

S. Gaubert. Rational series over dioids and discrete event systems. In Lecture Notes in Control and Information Sciences, vol. 199, Springer Verlag, 1994.

13

B. Gaujal, M. Jafari, M. Baykal-Gürsoy, and G. Alpan. Allocation sequences of two processes sharing a resource. Submitted, 1995.

14

B. Gaujal and A. Jean-Marie. Strategies for load balancing in distributed computation with associative operations. In Proc. of QMIPS, London, 1994.

15

B. Gaujal, A. Jean-Marie, and J. Mairesse. Minimal representation of uniform recurrence equations. In preparation, 1995.

16

P. Glasserman and D. D. Yao. Monotone Structure in Discrete-Event Systems. John Wiley and Sons, New York, 1994.

17

A. Jean-Marie and W. Massey. Steady state analysis for a series queueing network with blocking. 1994.

18

J. Mairesse. Products of irreducible random matrices in the (max,+) algebra - part i. Technical Report 1939, INRIA, Sophia Antipolis, France, 1993.

19

J.-E. Pin. Finite semigroups and recognizable languages: an introduction. Technical Report LIAFA 94.15, Laboratoire informatique théorique et programmation, Institut Blaise Pascal, 4, Place Jussieu, 75252 Paris, 1994.

20

P.J. Ramadge and W.M. Wonham. Supervisory control of discrete event processes. In D. Hinrichsen and A. Isidori, editors, Feedback Control of Linear and Nonlinear Systems, Lecture Notes on Control and Information Sciences No. 39, pages 202--214. Springer Verlag, 1982.

21

P.J. Ramadge and W.M. Wonham. Supervisory control of a class of discrete event processes. SIAM J. Control and Optimization, 25:206--230, 1987.

22

W. Reisig. Petri nets. Springer Verlag, 1985.

23

B. De Schutter and B. De Moor, ``The characteristic equation and minimal state space realization of SISO systems in the max algebra,'' in Proceedings of the 11th International Conference on Analysis and Optimization of Systems, Sophia-Antipolis, France, vol. 199 of Lecture Notes in Control and Information Sciences, pp. 273--282, Springer-Verlag, 1994.

24

B. De Schutter and B. De Moor, ``Minimal realization in the max algebra is an extended linear complementarity problem,'' Systems & Control Letters, vol. 25, no. 2, pp. 103--111, May 1995.

25

R. Smedinga. An overview of results in Discrete event systems using a trace theory based setting. In S. Balemi, P.Kozàk, and R. Smedinga, editors. Discrete Event Systems: Modeling and Control. Birkhä user, Basel, 1993, pp 43-56.

26

R. Smedinga. Effective control of logical discrete event systems in a trace theory setting using the reflection operator. In G. Cohen and J.-P. Quadrat, editors. 11th International Conference on Analysis and Optimization of Systems, Discrete Event Systems. Springer Verlag, 1994, pages 66-72.

...BRIMS

Basic Research Institute in the Mathematical Sciences