System Modelling and Analysis

Recommended Prerequisites

Theory of Computation, Statistics.

Teaching Methods

Teaching is organised as two complementary components, theory and practice.. Lectures (T) are mainly of an expository nature, but are also used to answer questions of general interest to the class. Practical (PL) sessions serve to consolidate the concepts presented in the lectures through modelling and analysis exercises, both on paper and on the computer, using suitable modelling software. A number of (assessed) problem-solving assignments involving the modelling and analysis of simplified, but realistic, systems.

Learning Outcomes

Real-world problem solving is increasingly based on mathematical abstractions which, through suitable manipulation, lead to results which can be translated back to the real world. This course unit focuses on models for system analysis, with emphasis on optimisation models and discrete event systems, and with application to the four main areas of the programme. Students should become able to:

1) formulate optimisation problems, placing them into appropriate categories based on their characteristics, and formalising them so as to allow them to be solved by the most appropriate methods.

2) model and analyse simple traffic, manufacturing, computer (hardware and software) and communication systems as discrete event systems.

In addition, students should develop skills in analysis and synthesis, problem solving, critical reasoning and self-learning, as well as the ability to apply the theoretical knowledge acquired to concrete practical settings.

Work Placement(s)

No

Syllabus

Part I – Optimisation Models

1. Non-linear programming: concepts and general results for the unconstrained and constrained cases.

2. Linear programming: formalisation; duality; applications.

3. Integer linear programming: unimodularity; cut planes; applications.

4. Dynamic programming: concepts; Bellman's principle of optimality; applications.

Part II – Discrete Event Systems (DES)

5. Systems and models: concepts; types of systems; DES and application examples.

6. Finite-state automata: Language models of DES; analysis of DES based on finite-state automata.

7. Petri nets: definition; comparison with automata; analysis of Petri nets.

8. Timed and hybrid models: timed automata and timed Petri nets; dioid algebras; hybrid models.

9. Stochastic timed automata.

10. Markov chains: discrete-time and continuous-time Markov chains.

11. Introduction to queueing theory.

Head Lecturer(s)

Carlos Manuel Mira da Fonseca

Assessment Methods

Assessment
Resolution Problems: 30.0%
Exam: 70.0%

Bibliography

George L. Nemhauser and Laurence A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999 .

Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.

Mordecai Avriel, Nonlinear Programming: Analysis and Methods, Dover Publications, 2003.

Christos G. Cassandras and Stéphane Lafortune, Introduction to Discrete Event Systems, Springer, 2007.

Branislav Hrúz and MengChu Zhou, Modeling and Control of Discrete-event Dynamic Systems: with Petri Nets and Other Tools, Springer, 2007.