Discrete Event Systems, 2017-2018

Master of Science in Engineering

Università di Siena

Automata and Queueing Systems

Discrete Event Systems

October 2017 - January 2018

1 News
2 About the instructor
    2.1 Instructor
    2.2 Office hours
3 About the course
    3.1 Training objectives
    3.2 Required background
    3.3 Organization
    3.4 Syllabus
    3.5 Didactic methods
    3.6 Reference text
4 Exams
    4.1 Learning assessment procedures
    4.2 Tests
    4.3 Results
5 Teaching material
    5.1 Lecture notes
    5.2 Exercises with solutions
6 About the lectures
    6.1 Timetable
    6.2 Lecture schedule

1 News

NEW! The results of the written test of September 7th, 2018 are available in Section 4.3.
- See Section 4.1 for the learning assessment procedures.
- Students who passed the written test are requested to send an email to the Instructor to schedule a date for the oral 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 4850 ext. 1020
	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

The main course is DISCRETE EVENT SYSTEMS.
- CFU: 9
- Duration: ∼ 72 hours
- Students: MSc CAE-R&A
The course AUTOMATA AND QUEUEING SYSTEMS is a subset of the main course.
- CFU: 6
- Duration: ∼ 48 hours (i.e. the first 48 hours of the main course)
- Students: MSc CAE-IS, MSc EM

3.4 Syllabus

ALL ( ∼ 48 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 ( ∼ 24 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 both
- 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 both
- 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 on the first exam date in the winter session of exams.

4.2 Tests

Past courses

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

Endterm test of December 20th, 2017: 1) ; 2) (with solutions)
Endterm/full test of February 8th, 2018
Full test of March 2nd, 2018

4.3 Results

5 Teaching material

5.1 Lecture notes

Version 0.3 (last update: October 27, 2015)
- The notes will be constantly 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

Monday - from 4PM to 6PM (room F)
Wednesday - from 2PM to 5PM (room F)
Thursday - from 11AM to 1PM (room F)

6.2 Lecture schedule

Date	Topics	Where to study (B = book; LN = lecture notes)	Additional material
October 2, 2017 (2h)	Presentation of the course		Slides
October 4, 2017 (3h)	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 Discrete Event System (DES)	[B] Chapter 1 (except §1.2.7, §1.2.8 and §1.3.5) [LN] Chapter 1
October 5, 2017 (2h)	Untimed models of DES: state automata (with outputs) Graphical representation of state automata Example: queueing system	[B] Section 2.2.2 [B] Example 2.11 [LN] Chapter 2
October 9, 2017 (2h)	Exercises
October 11, 2017 (3h)	Introduction to event timing Example: FIFO vs Round-Robin queueing Definition of clock structure Timed models of DES: timed automata Basic examples of event timing dynamics	[B] Section 5.1 [B] Section 5.2 (only §5.2.1) [LN] Section 3.1
October 12, 2017 (2h)	Algorithm for event timing dynamics	[B] Section 5.2 (only §5.2.2, §5.2.4 and §5.2.5)
October 16, 2017 (2h)	Example: FIFO vs Round-Robin queueing (revisited)
October 18, 2017 (3h)	Exercises		Exercises (with solutions)
October 19, 2017 (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 23, 2017 (2h)	Uncertainty sources in models of DES Models of DES with uncertainty: stochastic timed automata	[B] Sections 6.1, 6.3 and 6.4
October 25, 2017 (2h)	Analysis of stochastic timed automata Example		Example
October 26, 2017 (2h)	The exponential distribution: definition and properties
October 30, 2017 (2h)	Stochastic timed automata with Poisson clock structure Distribution of residual lifetimes Distribution of interevent times Event probabilities State probabilities	[B] Section 6.8
November 2, 2017 (2h)	The Poisson counting process Stochastic timed automata with Poisson clock structure Distribution of state holding times	[B] Sections 6.6 and 6.7
November 6, 2017 (2h)	Exercise		Exercise
November 8, 2017 (3h)	Exercises		Exercises
November 9, 2017 (2h)	Exercises		Exercises
November 13, 2017 (2h)	Review of basic concepts of statistics Law of large numbers Histograms Random number generation via the inverse method
November 15, 2017 (3h)	Examples Estimation of the expected value of a random variable Estimation of a probability distribution Generation of samples from a given distribution
November 16, 2017 (2h)	Use of simulation for analysis of stochastic timed automata Estimation of state and event probabilities		Matlab files
November 20, 2017 (2h)	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 (only §7.3.1 and §7.3.4)
November 22, 2017 (3h)	Continuous-time homogeneous Markov chains Transition rate matrix and its properties State holding times Transition probabilities Estimation of transition rates State probabilities Graphical representation Classification of states	[B] Section 7.3 (from §7.3.5 to §7.3.9)
November 23, 2017 (2h)	Continuous-time homogeneous Markov chains 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 (only §7.3.10) [B] Section 7.4
November 27, 2017 (2h)	Simulation of stochastic timed automata (lab tutorial)		Exercise Matlab files
November 29, 2017 (3h)	Queueing theory Specification of queueing models A/B/m/K notation Transient and steady state analysis Characterization of steady state Performance indexes Little's law PASTA property	[B] Sections from 8.1 to 8.5	[B] Section 8.6
December 4, 2017 (2h)	Exercises		Exercises
December 6, 2017 (3h)	Discrete-time homogeneous Markov chains Chapman-Kolmogorov equations Transition probability matrix and its properties State holding times State probabilities Graphical representation	[B] Sections 7.1 and 7.2 (from §7.2.1 to §7.2.7)
December 7, 2017 (2h)	Discrete-time homogeneous Markov chains Classification of states Birth-death chains Steady state analysis	[B] Section 7.2 (from §7.2.8 to §7.2.10)
December 11, 2017 (2h)	Exercises		Exercises (with solutions)
December 13, 2017 (3h)	Exercises		Exercises (with solutions)
December 18, 2017 (2h)	Exercises		Exercises
December 20, 2017 (3h)	Endterm test
December 21, 2017 (2h)	Examples of hybrid models and applications

File translated from T_EX by T_TH, version 4.03.
On 20 Sep 2018, 11:51.