Discrete Event Systems in Dioid Algebra and Conventional Algebra E-Book

Philippe Declerck

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 178

Veröffentlichungsjahr: 2013

Beschreibung

This book concerns the use of dioid algebra as (max, +) algebra to treat the synchronization of tasks expressed by the maximum of the ends of the tasks conditioning the beginning of another task - a criterion of linear programming. A classical example is the departure time of a train which should wait for the arrival of other trains in order to allow for the changeover of passengers. The content focuses on the modeling of a class of dynamic systems usually called "discrete event systems" where the timing of the events is crucial. Events are viewed as sudden changes in a process which is, essentially, a man-made system, such as automated manufacturing lines or transportation systems. Its main advantage is its formalism which allows us to clearly describe complex notions and the possibilities to transpose theoretical results between dioids and practical applications.

Leseprobe

Contents

1 Introduction

1.1. General introduction

1.2. History and three mainstays

1.3. Scientific context

1.4. Organization of the book

2 Consistency

2.1. Introduction

2.2. Preliminaries

2.3. Models and principle of the approach

2.4. Analysis in the “static” case

2.5. “Dynamic” model

2.6. Extremal acceptable trajectories by series of matrices

2.7. Consistency

2.8. Conclusion

3 Cycle Time

3.1. Objectives

3.2. Problem without optimization

3.3. Optimization

3.4. Conclusion

3.5. Appendix

4 Control with Specifications

4.1. Introduction

4.2. Time interval systems

4.3. Control synthesis

4.4. Fixed-point approach

4.5. Algorithm

4.6. Example

4.7. Conclusion

5 Online Aspect of Predictive Control

5.1. Introduction

5.2. Control without desired output (problem 1)

5.3. Control with desired output (problem 2)

5.4. Control on a sliding horizon (problem 3): online and offline aspects

5.5. Kleene star of the block tri-diagonal matrix and formal expressions of the sub-matrices

5.6. Conclusion

Bibliography

List of Symbols

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2013

The rights of Philippe Declerck to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2012948947

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISSN: 2051-2481 (Print)

ISSN: 2051-249X (Online)

ISBN: 978-1-84821-461-3

1

Introduction

1.1. General introduction

The main motivation of this book is the modeling of a class of dynamic systems usually called “discrete event systems” where the timing of the events is crucial. Events are viewed as sudden changes in the process, which is essentially a man-made system, such as automated manufacturing lines or transportation systems. Forming the core of the following sections, the synchronization of the tasks is expressed by the maximum of the ends of the tasks conditioning the beginning of another task. A classical example is the departure time of a train that should wait for the arrival of other trains in order to allow for the changeover of passengers. The basic idea of dioid algebra is to treat the maximum as an operation that is included in algebra, here the (max, +) algebra. A large part of this book concerns this topic. Another fundamental idea is to treat the maximum in a maximization of a criterion as in linear programming. We also focus on this second topic in this book.

1.2. History and three mainstays

This book is based on the three following mainstays:

– Well developed in the European and French scientific community, the topic of dioid algebra as (max, +) algebra has existed for the past three decades. Its main advantage is its formalism that allows us to clearly describe complex notions and the possibility of transposing theoretical results between dioids and practical applications. Only a few books have been written on this subject. The first was written by R.A. Cuninghame-Green in 1979. We can quote in graph theory the important books of Gondran and Minoux (Chapter 3 in [GON 84] and [GON 02]). At the origin of the “French school”, another book [BAC 92] was written from the system- theoretical point of view in 1992. Finally, the last book focuses on the transportation systems and was produced in 2006 by a team working in the Netherlands [HEI 06].

– In conventional algebra, linear programming is the oldest for which we can quote the famous French mathematician and physicist Joseph Fourier (1768–1830) for his work at the beginning of the 19th Century (Fourier–Motzkin algorithm). However, this topic is still current and the IT community has produced many algorithms that have efficiently solved bivariable linear systems for the past three decades.

– The third mainstay is the Petri net, which has its origin in Carl Adam Petri’s dissertation submitted in 1962 in West Germany (Carl Adam Petri 1926–2010). A Petri net is a graphical modeling tool that describes complex discrete event systems with various themes and application fields. This topic has been well developed for the past three decades in Europe.

1.3. Scientific context

We describe below the main concepts that will determine the following studies in the mathematical field and Petri nets. The modeling of the time behaviors will also play an important role.

Figure 1.1.Three topics

1.3.1. Dioids

Figure 1.2.Two algebras: common core and fundamental difference

1.3.2. Petri nets

In the field of discrete event systems, the Petri net allows the modeling of many types of industrial process, transportation system, electronics system, etc. A classical classification of Petri nets can be made with respect to the following two fundamental types (T. Murata gives a good overview of this subject in [MUR 89]).

– The event graphs (each place has exactly one in-going transition and one out-going transition) highlight the synchronization, but no choice is possible. The introduction of time is possible in this model and complex synchronizations can be considered. We will choose this model in the following chapters.

– The state graphs (each transition has exactly one in-going place and one out-going place) consider the choices but do not model the synchronization. The logical aspect is an important characteristic in this model, but the introduction of time is not easy.

– The intersection of the two classes is not empty but only contains Petri nets that do not express either the synchronization or the choice. Therefore, event graphs and state graphs are two fundamental models that equally determine two research fields.

Figure 1.3.Keystructures in Petri nets

1.3.3. Time and algebraic models

All processes naturally present a time evolution and the introduction of time in Petri nets constitutes an important motivation. There are also many everyday examples such as the arrival of students to a course (see Chapter 4 on control). However, the direct introduction of time in general Petri nets quickly leads to a combinatorial blow up of the state-space, which reduces the application field. Contrary to Model Checking, which generates an origin at each event (firing transition) in complex systems, we consider below a unique origin time. Moreover, we will consider specific time models where we can establish a complete algebraic model.

In the field of Petri nets, P-time event graphs, T-time event graphs and time stream event graphs allow us to describe complex synchronizations and to model processes in the production industry, microcircuit design, transportation systems, the food industry or multimedia under the time aspect. The state trajectory is not determined by the iteration of a state equation but is described by a space evolution expressed by the iteration of an interval. The bounds are defined by functions using the minimum, maximum and addition operations. These models are called “interval models”. The models obtained are not only (max, +) models but also (min, max, +) models.

Note that the choice of analysis of these models comes from the choice of the use of the “dater”, that is, to describe each event by a numbered date or to note by a “counter”, i.e. the number of events at each moment. This choice affects the initial modeling, which is a delicate step as it can lead to an unusable model. Note that it is always possible to numerically convert a trajectory expressed with daters into counters, and vice versa. A consequence is that the following chapters will describe complex phenomena of synchronization for Petri nets presenting simple structures. The dual remark is symmetrical: the choice of the counters leads to the analysis of Petri nets presenting complex structures, weights on the arcs but simple synchronizations.

From a mathematical point of view, we consider the real space and use the following algebras, that is ( ∪ {– ∞}, max, +), and ( ∪ {– ∞}, min, max, +), possibly completed with +∞. On the other hand, the counters are defined over the integers and not the real numbers. In that case, we consider algebra as ( ∪ {+∞}, min, +) or ( ∪ {+∞}, min, +) possibly completed with –∞. Remember that the integer linear programming problems need specific techniques.

Figure 1.4.Daters and counters

1.4. Organization of the book

Figure 1.5 presents the chapters of the book focusing on time models based on daters. We consider the liveness problem as a bad modeling or incorrect parameters which can lead to the absence of a time evolution. The cycle time is the subject of Chapter 3 as it gives an interesting picture of the efficiency of the system. The aim is also to control the process and this point is described in the final chapters.

A comparison of the different classes of time event graphs will be presented at the beginning of chapters on consistency and control as our main interest is on the algebraic models that can describe a broad spectrum of Petri nets. In this book, we also focus on the efficiency of the proposed algorithms: different discussions about complexity and CPU time will be given in the chapters on liveness and predictive control. We also describe some pedagogical examples that will illustrate the main concepts and suggest some new ideas. Each chapter is almost autonomous and the reader only needs to read the preliminary remarks of the chapter on consistency. The book ends with a bibliography and a list of frequently used symbols.

Figure 1.5.Chapters of the book

2

Consistency

In this chapter, we consider the (max, +) model of P-time event graphs whose behaviors are defined by lower- and upper-bound constraints. The extremal trajectories of the system starting from an initial interval are characterized by a particular series of matrices for a given finite horizon. Two dual polynomial algorithms are proposed to check the existence of feasible trajectories. The series of matrices are used in the determination of the maximal horizon of consistency and the calculation of the date of the first token deaths.

2.1. Introduction

2.1.1. Models

Petri nets (PNs) with time can express the time behavior of discrete event systems with their specifications. Two main behaviors of the transitions can be distinguished: firing as soon as possible in timed PNs and firing in given time intervals for time PNs. Time can be associated with places, transitions and arcs of the PNs. In time stream PNs, temporal intervals are associated with arcs out-going from places and the firing interval of transitions is defined by different semantics [COU 96, DIA 97]. For timed PNs, durations can be associated with places (P-timed PNs) or transitions (T-timed PNs) and the relevant subclasses are equivalent. For time PNs, temporal intervals can similarly be associated with places or transitions but the corresponding subclasses (P-time PNs and T-time PNs) are fundamentally different. In time PNs, a temporal interval of firing is associated with each transition enabled by the marking while a temporal interval of availability is associated with each token that enters a place in P-time PNs (Chapter 6 in [DIA 97]).