Master of Science in Engineering
University of Siena
Automata and Queueing Systems
Discrete Event Systems
October 2016 - January 2017

    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


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


3  About the course

3.1  Training objectives

3.2  Required background

3.3  Organization

3.4  Syllabus

    ALL ( ∼ 48 hours)
    CAE-R&A only ( ∼ 24 hours)

3.5  Didactic methods

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
    Midterm test, endterm test and project

4.2  Tests

    Past courses

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

Date
Topics
Where to study
  (B = book; LN = lecture notes)  
  Additional material  
October 3, 2016 (2h)
  • Presentation of the course     
 
  • Slides    
October 4, 2016 (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, 2016 (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 10, 2016 (2h)
  • Exercises
 
  • Exercises (with solutions)   
October 11, 2016 (3h)
  • Introduction to event timing
  • Example: FIFO vs Round-Robin queueing
  • Definition of clock structure
  • Timed models of DES: timed automata
   [B] Section 5.1
   [B] Section 5.2 (only §5.2.1)
   [LN] Section 3.1
 
October 12, 2016 (2h)
  • Basic examples of event timing dynamics
  • Algorithm for event timing dynamics
   [B] Section 5.2 (only §5.2.2, §5.2.4 and §5.2.5)  
October 17, 2016 (2h)
  • Example: FIFO vs Round-Robin queueing (revisited)
   
October 18, 2016 (3h)
  • Exercises
 
  • Exercises (with solutions)   
October 19, 2016 (2h)
  • Review of probability theory
   [B] Appendix I (except §I.7 and §I.8)
  • Note di calcolo delle probabilità (in Italian)   
October 24, 2016 (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, 2016 (3h)
  • Analysis of stochastic timed automata
  • Example
 
  • Example     
October 26, 2016 (2h)
  • The exponential distribution: definition and properties
   
November 7, 2016 (2h)
  • Stochastic timed automata with Poisson clock structure
    • Distribution of residual lifetimes
    • Distribution of interevent times
    • Distribution of events
    • Distribution of states
   [B] Section 6.8  
November 8, 2016 (3h)
  • The Poisson counting process
  • Stochastic timed automata with Poisson clock structure
    • Distribution of state holding times
  • Example
   [B] Sections 6.6 and 6.7  
November 9, 2016 (2h)  
  • Exercise
 
  • Exercise (with solutions)     
November 14, 2016 (2h)  
  • Exercises
 
  • Exercises (with solutions)     
November 15, 2016 (3h)  
  • Exercises
 
  • Exercises (with solutions)     
November 16, 2016 (2h)  
  • Exercises
 
  • Exercises (with solutions)     
November 21, 2016 (2h)  
  • Midterm test (ALL)
   
November 22, 2016 (3h)
  • 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 23, 2016 (2h)
  • Continuous-time homogeneous Markov chains
    • Transition rate matrix and its properties
    • State holding times
    • Transition probabilities
    • Estimation of transition rates
   [B] Section 7.3 (only §7.3.5, §7.3.6 and §7.3.7)     
November 28, 2016 (2h)
  • Continuous-time homogeneous Markov chains
    • State probabilities
    • Graphical representation
    • Classification of states
   [B] Section 7.3 (only §7.3.8 and §7.3.9)     
November 29, 2016 (3h)
  • 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
  • Example
   [B] Section 7.3 (only §7.3.10)   
   [B] Section 7.4   
  • Exercises (with solutions)     
  • Matlab files
November 30, 2016 (2h)  
  • Use of simulation for analysis of stochastic timed automata     
    • Law of large numbers
    • Estimation of state and event probabilities
   
December 6, 2016 (3h)
  • Queueing theory
    • Specification of queueing models
    • A/B/m/K notation
    • Transient and steady state analysis
    • Characterization of steady state
    • Performance of queueing systems
    • Little's law
    • PASTA property
   [B] Sections from 8.1 to 8.5  
December 7, 2016 (2h)
  • Examples of Markovian queueing systems
  • Exercises
   [B] Section 8.6
  • Exercises (with solutions)     
December 19, 2016 (2h)
  • Simulation of stochastic timed automata (lab tutorial)
 
  • Matlab files
December 21, 2016 (2h)
  • Simulation of stochastic timed automata (lab tutorial)
 
  • Exercise
  • Matlab files
January 9, 2017 (2h)
  • Discrete-time homogeneous Markov chains
    • Chapman-Kolmogorov equations
    • Transition probability matrix and its properties
    • Graphical representation
   [B] Sections 7.1 and 7.2 (from §7.2.1 to §7.2.4)  
January 10, 2017 (3h)
  • Discrete-time homogeneous Markov chains
    • State probabilities
    • State holding times
    • Classification of states
   [B] Section 7.2 (from §7.2.5 to §7.2.8)  
January 16, 2017 (2h)
  • Discrete-time homogeneous Markov chains
    • Steady state analysis
    • Applications to robotics
   [B] Section 7.2 (from §7.2.9 to §7.2.10)  
January 17, 2017 (3h)
  • Exercises
 
  • Exercises (with solutions)     
January 18, 2017 (2h)
  • Exercises
   [B] Example 7.2
  • Exercises (with solutions)     
January 31, 2017 (1h)  
  • Endterm test (CAE-R&A only)
   



File translated from TEX by TTH, version 4.03.
On 25 May 2017, 13:09.