Bachelor and Master Theses

Title: Offline Scheduling of Task Sets with Complex End-to-End Delay Constraints
Subject: Computer Science
Level: Advanced
Description: Software design for automotive systems is highly complex. Applications in this domain are often safety critical and have strict timing requirements.
They are designed using periodically occurring tasks, each task having its own deadline.
In addition, many such applications are subject to end-to-end timing constraints. This means, timing requirements exist on a chain of independently triggered tasks. Such tasks can have different periods which leads to over- and under-sampling situations. This makes the analysis non-trivial.
In [1] it is shown how such systems can be analysed and how job-level dependencies (enforced dependencies between selected task instances) can be generated such that the end-to-end timing constraints are always met. These concepts are implemented in the MECHAniSer tool [2] and build the starting point for the thesis work (
This thesis focuses on the problem of scheduling such applications on a single core platform. As first outcome, an offline schedule shall be generated such that all tasks meet their deadlines and all job-level dependencies are met. This will be done by formulating the scheduling problem using the notion of Conditional Time-Intervals [3, 4] which are supported by the IBM ILOG CP Optimizer.
A second part will focus on the execution of the generated offline schedule on a real hardware platform.

Expected main results:
• Literature review
• Formulating the scheduling problem using Conditional Time-Intervals, possibly including additional constraints such as maximum size of the offline-schedule.
• An execution framework for the generated offline schedule on a real HW platform
• An extensive evaluation
• A written thesis

• Programming knowledge (preferably C and Java)
• Knowledge about real-time systems

The thesis can be adapted for 1-2 students and for 15 or 30CP.

[1] M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte, “Synthesizing job-level dependencies for automotive multi-rate effect chains,” in 22th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2016.

[2] M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte. “MECHAniSer - a timing analysis and synthesis tool for multi-rate effect chains with job-level dependencies”. In 7th International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS).

[3] P. Laborie, J. Rogerie. “Reasoning with Conditional Time-Intervals”. In 21st International Florida Artificial Intelligence Research Society Conference (FLAIRS’08), 2008.

[4] P. Laborie, J. Rogerie, P. Shaw, and P Vilim. “Reasoning with Conditional Time-Intervals. Part II: An Algebraical Model for Resources”. In 22st International Florida Artificial Intelligence Research Society Conference (FLAIRS’09), 2009.
Prel. end date: 2017-06-09
Presentation date: 2017-06-01
Student: Jonas Holmberg
IDT supervisor: Matthias Becker, 076-781 16 04
Examinator: Saad Mubeen
Saad Mubeen, +4621103191

Rapport och bilagor


Senaste uppdatering



2017-06-09, 16:04

  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2018.08.31