Discrete Event Systems, 2020-2021

Master of Science in Engineering

Università di Siena

Automata and Queueing Systems

Discrete Event Systems

October 2020 - January 2021

1 News

The midterm test (for A&QS only) is scheduled Monday, November 16 during lecture hours.
- Students are required to register for the test by filling the following Google form by Wednesday, November 11.
- The test will be held online only. Instructions to attend the test will be provided to registered students on Thursday, November 12.
- Non-registered students will not be allowed to attend the test.
- For students not attending the test, the lecture of Monday, November 16 is cancelled.
Homework: do the entry test of probability theory available in Section 6.3 (lecture of October 22, 2020).
- [Optional] Send the test to the instructor for correction by October 29, 2020.
The course has started on October 1, 2020.
- All students are invited to register for the course by filling the following Google form.
- Students willing to attend the lectures online, find instructions in Section 6.2.
- Lectures will be recorded, and video recordings will be made available to the registered students.

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.
Tutorials will be an important part of this course to put into practice the studied tools.

3.2 Required background

Dynamical systems
Probability and statistics

3.3 Organization

DISCRETE EVENT SYSTEMS
- CFU: 9
- Duration: ∼ 72 hours
- Students: MSc A2-R&A
AUTOMATA AND QUEUEING SYSTEMS
- CFU: 6
- Duration: ∼ 54 hours (i.e. the first 54 hours of Discrete Event Systems)
- Students: MSc A2-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

A2-R&A only ( ∼ 18 hours)

Discrete-time Markov chains
Control applications of discrete event systems

3.5 Didactic methods

The course is organized in lectures (60%) and tutorials (40%).

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 two/three, to be solved in about 2.5 hours).
- Examples of past written tests (some with solutions) can be found in Section 4.2.
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 takes the performance in both tests into account.

Midterm/endterm test and project

The written test of the final exam of AUTOMATA AND QUEUEING SYSTEMS can be replaced with
- a midterm test (topics: logical, timed and stochastic timed models of DES), 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 DES; 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, 2019/20
In Italian: 2007/08, 2008/09, 2009/10, 2010/11, 2011/12

4.3 Results

No results available at the moment.

5 Teaching material

5.1 Lecture notes

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

5.2 Exercises with solutions

Exercises on state automata (last update: October 14, 2020)
Exercises on timed automata (last update: November 13, 2014)
Exercises on stochastic timed automata (last update: October 29, 2020)
Exercises on stochastic timed automata with Poisson clock structure (last update: November 14, 2014)
Exercises on discrete-time homogeneous Markov chains (last update: December 16, 2014)

6 About the lectures

6.1 Timetable

Monday - from 8:30AM to 12:00PM (room 145)
Thursday - from 12:00PM to 1:45PM (room 101)

6.2 How to attend online

Lectures will be streamed live on the platform Cisco Webex at the following link.
Access restrictions
- The virtual meeting room is locked: one has to wait in the lobby until admitted.
- Only registered students will be admitted from the lobby into the meeting. Please register for the course by filling the following Google form.
- Students are required to join the meeting before the start of the lecture. Admission into the meeting during the lecture is not guaranteed.
Instructions on the use of the platform Cisco Webex can be found here (in Italian) and here (in English).

6.3 Lecture schedule

Date	Topics	Where to study (B = book; LN = lecture notes)	Additional material
October 1, 2020 (1 slot)	Presentation of the course		Slides
October 5, 2020 (2 slots)	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 State automata as models of DES 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] Chapter 1
October 8, 2020 (1 slot)	Untimed models of DES: state automata (with outputs) Graphical representation Simulation scheme Feasible event sequences Exercises on state automata	[LN] Chapter 2	Exercises (with solutions)
October 12, 2020 (2 slots)	Exercises on state automata Introduction to timed models of DES Example: FIFO vs Round-Robin queueing	[B] Section 5.1 [LN] Section 3.1	Exercises (with solutions)
October 15, 2020 (1 slot)	Timed models of DES: timed automata Clock structure Basic examples of event timing dynamics	[B] Section 5.2 (only §5.2.1)
October 19, 2020 (2 slots)	Timed models of DES: timed automata Basic event timing mechanism Exercises on timed automata	[B] Section 5.2 (only §5.2.2, §5.2.4 and §5.2.5)	Exercises (with solutions)
October 22, 2020 (1 slot)	Review of basic concepts of probability theory	[B] Appendix I (except §I.7 and §I.8) [LN] Appendix A	Entry test of probability theory
October 26, 2020 (2 slots)	Uncertainty sources in models of DES Models of DES with uncertainty: stochastic timed automata Example of analysis of a stochastic timed automaton	[B] Sections 6.1÷6.5	Example
October 29, 2020 (1 slot)	Exercises on stochastic timed automata		Exercises (with solutions)
November 2, 2020 (2 slots)	The exponential distribution: definition and properties The Poisson counting process Stochastic timed automata with Poisson clock structure Distribution of residual lifetimes Conditional probability of the events	[B] Sections 6.6÷6.8
November 5, 2020 (1 slot)	Exercises on stochastic timed automata with Poisson clock structure		Exercises (with solutions)
November 9, 2020 (2 slots)	Stochastic timed automata with Poisson clock structure Distribution of state holding times Exercises on stochastic timed automata and Poisson processes		Exercises (with solutions)
November 12, 2020 (1 slot)	Exercises on stochastic timed automata and Poisson processes		Exercises (with solutions)
November 16, 2020 (2 slots)	Midterm test A&QS
November 19, 2020 (1 slot)	Stochastic timed automata with Poisson clock structure Event probabilities P(E_k=e) State probabilities P(X_k=x) Basics of stochastic processes Markov property and Markov processes	[B] Section 6.2
November 23, 2020 (2 slots)	Continuous-time homogeneous Markov chains Chapman-Kolmogorov equations Transition rate matrix and its properties Graphical representation State holding times Transition probabilities Transient analysis: state probabilities P(X(t)=x)	[B] Sections 7.1 and 7.3 (from §7.3.1 to §7.3.9)
November 26, 2020 (1 slot)	Continuous-time homogeneous Markov chains Classification of states Birth-death chains Steady state analysis	[B] Section 7.3 (only §7.3.10) [B] Section 7.4
November 30, 2020 (2 slots)	Concept of stochastic equivalence of discrete event models Stochastic equivalence of: Stochastic timed automata with Poisson clock structure Continuous-time homogeneous Markov chains Exercises on the use of stochastic equivalence in applications Review of basic concepts of statistics Law of large numbers Central limit theorem
December 3, 2020 (1 slot)	Review of basic concepts of statistics Probability estimation Empirical cumulative distribution functions Histograms and estimation of probability density functions		Matlab files
December 7, 2020 (2 slots)	Identification of discrete event models from data Simulation of stochastic timed automata Random number generation Sampling of discrete random variables Sampling of continuous random variables via the inverse method		Matlab files Homework
December 10, 2020 (1 slot)	Queueing theory Specification of queueing models A/B/m/K notation Transient and steady state analysis Characterization of steady state Little's law PASTA property	[B] Sections from 8.1 to 8.6
December 14, 2020 (2 slots)	Queueing theory Performance indexes Exercises on Markovian queueing systems Example of As-Is and What-If analysis		Exercises (with solutions)
December 17, 2020 (1 slot)	Discrete-time homogeneous Markov chains Chapman-Kolmogorov equations Transition probability matrix and its properties State probabilities and transient analysis Graphical representation Example: a simple phone-call process	[B] Sections 7.1 and 7.2 (from §7.2.1 to §7.2.7, except §7.2.5)
December 21, 2020 (2 slots)	Discrete-time homogeneous Markov chains State holding times Classification of states Birth-death chains Steady state analysis Exercises on discrete-time homogeneous Markov chains	[B] Section 7.2 (§7.2.5 and from §7.2.8 to §7.2.11)	Exercises (with solutions) Additional exercises (with solutions)
January 7, 2021 (2 slots)	Exercises on stochastic timed automata Exercises on discrete-time homogeneous Markov chains		Exercises Additional exercises (with solutions)

File translated from T_EX by T_TH, version 4.15.
On 09 Jan 2021, 19:24.