Discrete Event Systems, 2021-2022

Master of Science in Engineering

Università di Siena

Automata and Queueing Systems

Discrete Event Systems

October 2021 - January 2022

1 News

NEW: The endterm test (for DES only) is scheduled Wednesday, December 22 at 2 PM in room 124.
- Students are required to register for the test by filling the following Google form by Monday, December 20.
- The test will be held in presence only.
- Non-registered students will not be allowed to attend the test.
The timetable of the course has been changed. Check the new timetable in Section 6.1.
The course has started on October 6, 2021.
- All students are invited to register for the course by filling the following Google form.
- The lectures of the course will be given in presence only.
- Videos covering the contents of the course and additional material will be available here (only for 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

Linear algebra
Probability theory

A tutorial on these topics (and more...) can be found here.

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/3 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 into account the performance in both tests, with higher weight given to the oral test.

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 test and project is ≥ 18 and both grades ≥ 15 (out of 30).
One may repeat the 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, 2020/21
In Italian: 2007/08, 2008/09, 2009/10, 2010/11, 2011/12

Midterm test of November 18, 2021 (with solutions)
Endterm test of December 22, 2021 (with solutions)

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 15, 2021)
Exercises on timed automata (last update: October 27, 2021)
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, 2021)

6 About the lectures

6.1 Timetable

Monday - from 5:30 PM to 7:30 PM (room C/D/F)
Tuesday - from 8:30 AM to 10:00 AM (room C/D/F)
Thursday - from 4:15 PM to 7:30 PM (room 145)

6.2 Lecture schedule

Date	Topics	Where to study (B = book; LN = lecture notes)	Additional material
October 6, 2021 (1 slot)	Presentation of the course		Slides
October 11, 2021 (1 slot)	Basics of system theory Systems and (mathematical) models Static vs dynamical systems Concept of state Continuous-state vs discrete-state systems Concept of event Time-driven vs event-driven systems Definition of DES	[LN] Chapter 1 [B] Chapter 1 (except §1.2.7, §1.2.8 and §1.3.5)
October 12, 2021 (1 slot)	Untimed models of DES: state automata (with outputs) Definition of state automaton Graphical representation Simulation scheme Feasible event sequences Example: queueing system	[LN] Chapter 2 [B] § 2.2.2 [B] Example 2.11
October 13, 2021 (1 slot)	Exercises on state automata		Exercises (with solutions)
October 18, 2021 (1 slot)	Introduction to timed models of DES Example: FIFO vs Round-Robin queueing	[LN] Section 3.1 [B] Section 5.1
October 19, 2021 (1 slot)	Timed models of DES: timed automata Definition of timed automaton Clock structure Basic examples of event timing dynamics	[B] § 5.2.1
October 20, 2021 (1 slot)	Timed models of DES: timed automata Score of an event Basic event timing mechanism	[B] §5.2.2, §5.2.4, and §5.2.5
October 21, 2021 (1 slot)	Exercises on timed automata		Exercises (with solutions)
October 25, 2021 (1 slot)	Exercises on timed automata (cont'd) Uncertainty sources in models of DES	[LN] Appendix A [B] Section 6.1
October 26, 2021 (1 slot)	Models of DES with uncertainty: stochastic timed automata Definition of stochastic timed automaton Stochastic clock structure	[B] Sections 6.3, 6.4, and 6.5
October 28, 2021 (1 slot)	Example of analysis of a stochastic timed automaton		Example
November 4, 2021 (1.5 slots)	Exercises on stochastic timed automata The exponential distribution: definition and properties		Exercises (with solutions)
November 8, 2021 (1 slot)	Poisson clock structure Stochastic timed automata with Poisson clock structure Distribution of residual lifetimes Conditional probability of the events	[B] Section 6.8 (except §6.8.3)
November 9, 2021 (1 slot)	Stochastic timed automata with Poisson clock structure Distribution of state holding times The Poisson counting process	[B] Sections 6.6 and 6.7

File translated from T_EX by T_TH, version 4.12.
On 27 Jan 2022, 17:31.