Workshop on Max-Plus Algebra and its applications
About the Workshop
This workshop deals with the modelling and analysis of the time behaviour of linear systems which are nowadays characterized as ‘discrete event dynamic systems’ (DEDS). Such systems are usually man-made and consist of a finite number of resources (a resource could be a machine, a processor, a rail track). The central notion is formed by sequences of events, where events are viewed as sudden changes in a process to be studied. Examples are: a traffic light switches to red, arrival of an e-mail message, a train leaves the station. Such sequences can be subject to synchronization constraints (one event happening after the other; one train awaiting the arrival of another one in order to allow a change-over of passengers). These constraints make it impossible to describe DEDS within the context of differential equations and conventional algebra, as is the case with physical phenomena. The adjective ‘linear’ in ‘linear systems’ or ‘linear DEDS’ must be understood with respect to this latter algebra. Important subclasses of Petri nets and of queuing networks fall within this category of system.
The theory of linear discrete event systems (based on max-plus algebra) mimics the conventional linear systems theory (based on ‘conventional’ algebra) in many ways. For instance, stability issues, input/output behaviour, asymptotic behaviour and transfer matrices are important notions in both classes of systems. Graph theory is a helpful tool for proving and interpreting various results for DEDS.
Examples will be drawn from the design of timetables for trains, capacity issues for railways systems, and the synchronization of traffic lights in a city. Other applications concern production lines and communication networks.
The content of the workshop is split up into six parts:
1. Introduction and motivation by means of various examples.
2. Max-plus algebra and analysis.
3. Numerical procedures for solving large-scale problems.
4. Petri nets as a modelling tool.
5. Real size applications (emphasis on the timetabling design).
6. Extensions (stochastic systems, min-max-plus systems, …).
Other notions that will be dealt with are: recurrence relations,
timed Petri nets, Howard’s algorithm, allocation of trains,
asymptotic growth rate, circuit weight, Lyapunov coefficient,
eigenvalue, cycle time, Digraph, strongly connected graphs, token
distribution, non-expansive mappings, just in time solution,
recovery matrix, bipartite system, stability margin, software tools,
Perron-Frobenius, transient time, z-transform, railway system, line
and synchronization data, propagation of days, throughput, capacity
assessment.
Participants will receive a copy of the course sheets, as well as a copy of the manuscript ‘Max Plus at Work’.
The presenter
Geert Jan Olsder received his MSc and PhD degrees in applied mathematics from Groningen University, The Netherlands, (in 1968 and 1971, respectively). Currently he is professor of mathematical systems theory at Delft University of Technology; from 1999 onwards he has also been the deputy vice-chancellor at the same university. He is the co-author of the books ‘Dynamic Noncooperative Game Theory’, last edition SIAM, 1999; ‘Synchronization and Linearity’, Wiley, 1992; ‘Mathematical Systems Theory’, Delft University Press, last edition 2004; ‘Max Plus at Work’, to be published by Princeton University Press. He has also edited a number of books and is on the editorial boards of various scientific journals (among which is Environmental Modeling and Assessment).
Who should attend?
The workshop should be of interest to (applied) mathematicians, operations researchers, computer scientists, econometricians, civil, electrical and mechanical engineers with a quantitative background. Apart from this, being able to think in mathematical terms, whether you are a professor, practitioner or student, is more important than having a specific background.
Prerequisites
Most important is a basic knowledge of conventional algebra and matrix theory, with the addition of some knowledge of systems theory (or recurrence relations). Some knowledge of stochastic processes is required for a part in the extensions (see the contents) only. No prior knowledge of Petri nets or graph theory is required.
The venue
The event will be held in the General Purpose building, Level 1, Room GP1-08, Mawson Lakes Campus of the University of South Australia. Lunch and two coffee breaks will be provided.
Adelaide Information
Adelaide is the capital city of South Australia, and is a city of approximately one million people, with three universities and two Science Parks. The city of Adelaide is situated on St. Vincent Gulf in South Australia and has a Mediterranean style climate with hot dry summers and mild winters. Popular activities including wine tasting in the Barossa and Clare Valleys and the Southern Vale Districts, where many of Australia’s finest wines are made. There are numerous sightseeing and bush-walking opportunities in the Adelaide Hills, with Cleland Conservation Park and the magnificent Warrawong Sanctuary among the most popular attractions. There is easy access to the nearby Southern coast with whale spotting at Victor Harbor one of the most rewarding activities.