This tutorial explains the use of mixed integer linear programming (MILP) to model and solve time-triggered scheduling problems found in real-time embedded systems. First of all, we will show a simple Branch and Bound algorithm to illustrate the internal behavior of typical solver. The rest of the tutorial will be devoted to modeling of practical examples sharing CPUs, memories and communication channels. We will concentrate on time-triggered communication protocols and multicores while considering time constraints and periods of tasks and messages. Most of the examples given are formulated by graph formalisms and should be easy to understand without any specific knowledge of this field.


In this tutorial, we will show examples, explain basic theory, and we will do exercises to explore:

MILP as a combinatorial problem, Branch and Bound algorithm

Problem formulation using MILP

Time-triggered communication protocols modeling - Profinet and ZigBee

Predictable execution model on multicores

Periodic scheduling on heterogeneous resources


Zdenek is interested in time-triggered rela-time systems, scheduling and optimization. He has supervised 17 Ph.D. students and currently he is supervising 7 Ph.D. students. He is teaching a master’s course on Combinatorial Optimization with 120 students per year. Zdenek is currently a Head of the Industrial Informatics Department at CIIRC CTU in Prague. He is author or co-author of more than 30 journal papers and many conference papers. He chaired or co-chaired several international conferences (MISTA, EUROSYS, ECRTS, WPDRTS). Besides this, Zdenek acted as the founder of the Mechatronic Group, part of the Porsche Engineering Services in Prague. The Group grew up into a respectable facility with the core expertise in software development. Zdenek left, after 3 years of service, on his own accord as he decided to take on new challenging activities in research with a wider scope of industrial partners. He overtook a leadership of Merica company in 2013, which is strongly involved in the design of the optimization algorithms and development of SW for automotive.

Email: Zdenek.Hanzalek@cvut.cz

Website: https://rtime.felk.cvut.cz/~hanzalek/