Discrete Event Systems
Automata and Queueing Systems 2015/16
Master of Science in Engineering – University of Siena
About the instructor
Dr. Simone Paoletti
office: room 229 (2ndfloor, building San Niccolò) email: paoletti@dii.unisi.it
web page: http://www3.diism.unisi.it/~paoletti/
office hours: see the web page
Find the differences…
“time-driven” dynamics “event-driven” dynamics x(t): temperature in a room x(t): # of customers in a queue
Master of Science in Engineering – University of Siena
Time-driven vs Event-driven
• Time-driven dynamics are typically described by differential equations, e.g.
• What about event-driven dynamics?
0 0
) (
) ( ) ( )
(
x t x
t Bu t Ax t
x
- LTI state space equations -
Objectives of the course
Which types of models will be considered?
• Logical and timed models (automata)
• Markov chains
Main application: queueing theory Main contents:
• modelling
• probability
• programming (Matlab)
Modelling, simulation, analysis of Discrete Event Systems (DES)
Master of Science in Engineering – University of Siena
Examples of discrete event systems
(1/3)• a manufacturing plant with machines, workers, conveyor belts, buffers, etc.
• a bank with different types of customers and services (desks, ATMs, etc.)
• an airport with passengers in different states (check-in, security control, gate, boarding, etc.)
Examples of discrete event systems
(2/3)• a switching control system where it is possible to switch between different controllers
• an electronic component subject to deterioration and failures
• etc.
Master of Science in Engineering – University of Siena
Examples of discrete event systems
(3/3)Summarizing, discrete event systems can be found in:
• control systems
• manufacturing systems
• computer systems
• information networks
• transportation networks
• communication networks
• etc.
Just for fun…
Master of Science in Engineering – University of Siena
About the course
• Automata and Queueing Systems (6 CFU, ~ 48 hours)
MSc Computer and Automation Engineering - 1styear – Curriculum Information Systems
LM Ingegneria Gestionale - 1styear
• Discrete Event Systems (9 CFU, ~ 72 hours)
MSc Computer and Automation Engineering - 1st year –
Syllabus
• Logical models of DES
• Timed models of DES
• Stochastic timed models of DES
• Continuous-time Markov chains
• Queueing theory
• Markovian queueing networks
• Discrete-time Markov chains
• Control applications of DES
~ 48 hours (ALL)
~ 24 hours (CAE-R&A only)
Timing: ~ 75% lectures and exercises, ~ 25% lab tutorials
Master of Science in Engineering – University of Siena
Prerequisites and teaching material
Basic background:
• Dynamical systems
• Probability
Textbook:
C.G. Cassandras, S. Lafortune,
“Introduction to discrete event systems”, 2nded.
Springer, 2008
+ lecture notes available on-line
Final exam
• The final exam is both written and oral
Admission to the oral exam is subject to passing the written exam with a grade ≥18 (out of 30)
The oral exam should be given within the same session as the written exam
• The written exam may consist of:
exercises “on the paper”
exercises with Matlab
• The language for the oral exam can be either English or Italian
Master of Science in Engineering – University of Siena
Midterm exam and project
• The final written exam can be substituted with:
midterm written exam (after first half of the course)
project using Matlab (at the end of the course)
• Admission to the oral exam is subject to passing the midterm written exam and the project with an average grade ≥18 and both grades ≥15 (out of 30)
Course schedule
Duration: from October 5, 2015 to January 13, 2016
• Monday – from11AMto1PM (room F)
• Tuesday – from9AMto11AM (room F)
• Wednesday – from10AMto1PM (room 101)
Web-page
General information, lecture notes, exercises, past exams, etc.
are available on the course web page:
http://www3.diism.unisi.it/~paoletti/teaching/sed/1516/index.html
Master of Science in Engineering – University of Siena