Discrete Event Systems, 2019-2020

Master of Science in Engineering

Università di Siena

Automata and Queueing Systems

Discrete Event Systems

October 2019 - January 2020

1 News

NEW: The results of the endterm test of February 14, 2020 are available in Section 4.3.
- See Section 4.1 for the learning assessment procedures.
- According to the learning assessment procedures, students who did not pass the endterm test, are not entitled to a project, and will have to take the full test.

2 About the instructor

2.1 Instructor

	Simone Paoletti, PhD
	Assistant Professor
	Building: San Niccolò
	Floor: 2
	Room: 229 (red circle on the map)
	Email:
	Phone: 0577 23 5977
	Web: http://www3.diism.unisi.it/~paoletti/

2.2 Office hours

Contact the instructor via email.

3 About the course

3.1 Training objectives

Discrete event systems are systems whose dynamic behaviour is driven by asynchronous occurrences of discrete events.
Examples can be found in a variety of fields, such as control, computer science, automated manufacturing, and communication and transportation networks.
The aim of this course is to introduce several modelling, simulation and analysis tools for discrete event systems.
Lab tutorials with Matlab will be an important part of this course.

3.2 Required background

Dynamical systems
Probability

3.3 Organization

DISCRETE EVENT SYSTEMS
- CFU: 9
- Duration: ∼ 72 hours
- Students: MSc CAE-R&A
AUTOMATA AND QUEUEING SYSTEMS
- CFU: 6
- Duration: ∼ 54 hours (i.e. the first 54 hours of Discrete Event Systems)
- Students: MSc CAE-IS, MSc EM

3.4 Syllabus

ALL ( ∼ 54 hours)

Logical models of discrete event systems
Timed models of discrete event systems
Stochastic timed models of discrete event systems
Simulation of discrete event systems
Continuous-time Markov chains
Queueing theory
Markovian queueing networks

CAE-R&A only ( ∼ 18 hours)

Discrete-time Markov chains
Control applications of discrete event systems

3.5 Didactic methods

The course will be organized in lectures (50%) and tutorials, held both in class (25%) and in computer lab (25%).

3.6 Reference book

[CL08] C.G. Cassandras, S. Lafortune, "Introduction to discrete event systems". 2nd ed., Springer, 2008.

4 Exams

4.1 Learning assessment procedures

Final exam

The final exam consists of both a written test and an oral test.
The written test consists of exercises (typically three, to be solved in about 2.5 hours).
- Examples of past written tests (some with solutions) can be found in Section 4.2.
- Aid of Matlab is allowed (e.g. for matrix computations).
The oral test is a broad-spectrum discussion on the topics of the course, including theory and exercises.
- Enabled only if the grade of the written test is ≥ 18 out of 30.
- To be given within the same session as the written test.
- In case of failure, the student must repeat the written test.
- The language for the oral test can be either English or Italian.
The final grade is a weighted average of the grades of both tests.

Endterm test and project

The written test of the final exam of AUTOMATA AND QUEUEING SYSTEMS can be replaced with
- an endterm test (topics: logical, timed and stochastic timed models of DESs), and
- a Matlab project (topics: simulation; continuous-time Markov chains; queueing systems).
The written test of the final exam of DISCRETE EVENT SYSTEMS can be replaced with
- an endterm test (topics: logical, timed and stochastic timed models of DESs; discrete-time Markov chains), and
- a Matlab project (topics: simulation; continuous-time Markov chains; queueing systems).
Oral test enabled only if the average grade of endterm test and project is ≥ 18 and both grades ≥ 15 (out of 30).
One may repeat the endterm test in the winter session of exams.

4.2 Tests

Past courses

In English: 2012/13, 2013/14, 2014/15, 2015/16, 2016/17, 2017/18, 2018/19
In Italian: 2007/08, 2008/09, 2009/10, 2010/11, 2011/12

Endterm test of December 10, 2019 (with solutions)
Endterm/full test of January 30, 2020

4.3 Results

5 Teaching material

5.1 Lecture notes

Version 0.3 (last update: October 27, 2015)
- The notes will be updated during the course.
- Please always refer to the most updated version.

5.2 Exercises with solutions

Exercises on timed automata
Exercises on stochastic timed automata
Exercises on stochastic timed automata with Poisson clock structure
Exercises on discrete-time homogeneous Markov chains

6 About the lectures

6.1 Timetable

Tuesday - from 9AM to 1PM (room F)
Thursday - from 2PM to 4PM (room F)

6.2 Lecture schedule

Date	Topics	Where to study (B = book; LN = lecture notes)	Additional material
October 1, 2019 (2h)	Presentation of the course		Slides
October 3, 2019 (2h)	Introduction to Discrete Event Systems (DESs) Models Simulation Applications: As-Is and What-If analysis
October 8, 2019 (4h)	Basics of system theory Concept of system Static vs dynamical systems Concept of state Continuous vs discrete state Concept of event Time-driven vs event-driven systems Systems vs (mathematical) models Definition of DES Untimed models of DES: state automata (with outputs) Graphical representation of state automata Example: queueing system	[B] Chapter 1 (except §1.2.7, §1.2.8 and §1.3.5) [B] Section 2.2.2 [B] Example 2.11 [LN] Chapters 1 and 2
October 10, 2019 (2h)	Exercises on state automata
October 15, 2019 (4h)	Exercises on state automata (cont'd) Introduction to event timing Example: FIFO vs Round-Robin queueing	[B] Section 5.1 [LN] Section 3.1
October 17, 2019 (2h)	Definition of clock structure Timed models of DES: timed automata Basic examples of event timing dynamics	[B] Section 5.2 (only §5.2.1)
October 22, 2019 (4h)	Basic algorithm for event timing Exercises on timed automata	[B] Section 5.2 (only §5.2.2, §5.2.4 and §5.2.5)	Exercises (with solutions)
October 24, 2019 (2h)	Review of basic concepts of probability theory	[B] Appendix I (except §I.7 and §I.8)	Note di calcolo delle probabilità (in Italian)
October 29, 2019 (4h)	Uncertainty sources in models of DES Models of DES with uncertainty: stochastic timed automata Example: analysis of a stochastic timed automaton	[B] Sections 6.1, 6.3 and 6.4	Example
October 31, 2019 (2h)	Exercises on stochastic timed automata		Exercises (with solutions)
November 5, 2019 (4h)	Exercises on stochastic timed automata (cont'd) Review of basic concepts of statistics Law of large numbers Central limit theorem Probability estimation
November 7, 2019 (2h)	Random number generation Sampling of discrete random variables Sampling of continuous random variables via the inverse method
November 12, 2019 (4h)	Simulation of stochastic timed automata Lab tutorial Exercise		Matlab files Exercise
November 14, 2019 (2h)	Estimation of probability distributions Empirical cumulative distribution function Histograms Example of As-Is and What-If analysis		Matlab files
November 19, 2019 (4h)	The exponential distribution: definition and properties The Poisson counting process Stochastic timed automata with Poisson clock structure Event probabilities State probabilities Distribution of state holding times	[B] Sections 6.6, 6.7 and 6.8
November 21, 2019 (2h)	Exercises on stochastic timed automata with Poisson clock structure		Exercise (with solutions)
November 26, 2019 (4h)	Exercises on stochastic timed automata with Poisson clock structure (cont'd) Basics of stochastic processes Markov property and Markov processes Continuous-time homogeneous Markov chains Chapman-Kolmogorov equations	[B] Section 6.2 [B] Sections 7.1 and 7.3 (from §7.3.1 to §7.3.4)
November 27, 2019 (4h) ONLY MSc CAE-R&A	Discrete-time homogeneous Markov chains Chapman-Kolmogorov equations Transition probability matrix and its properties Graphical representation State holding times State probabilities and transient analysis Classification of states Birth-death chains	[B] Sections 7.1 and 7.2 (from §7.2.1 to §7.2.8)
November 28, 2019 (2h)	Continuous-time homogeneous Markov chains Transition rate matrix and its properties Graphical representation State holding times Transition probabilities Estimation of transition rates	[B] Section 7.3 (from §7.3.5 to §7.3.7)
December 3, 2019 (4h)	Continuous-time homogeneous Markov chains State probabilities and transient analysis Classification of states Birth-death chains Steady state analysis Equivalences between classes of models Stochastic timed automata with Poisson clock structure Continuous-time homogeneous Markov chains	[B] Section 7.3 (from §7.3.8 to §7.3.10) [B] Section 7.4
December 4, 2019 (4h) ONLY MSc CAE-R&A	Discrete-time homogeneous Markov chains Steady state analysis Exercises on discrete-time homogeneous Markov chains	[B] Section 7.2 (from §7.2.9 to §7.2.11)	Exercises (with solutions) Additional exercises (with solutions)
December 5, 2019 (2h)	Exercise on stochastic timed automata		Exercise (with solutions)
December 10, 2019 (3h)	Endterm test
December 17, 2019 (4h)	Queueing theory Specification of queueing models A/B/m/K notation Transient and steady state analysis Characterization of steady state Performance indexes Ergodicity Little's law PASTA property Exercises on Markovian queueing systems	[B] Sections from 8.1 to 8.6	Exercises (with solutions)

File translated from T_EX by T_TH, version 4.12.
On 26 Feb 2020, 09:26.