We address a range of schedulability analysis problems for multiprocessor real-time systems. As most of these problems are NP-complete and no efficient solutions have been so far proposed, we tackle these problems by employing mathematical optimization combined with the dynamic pruning of the solution search space. We show that such an approach results in solving algorithms of a significantly lower time and space complexity compared to other state-of-the-art solutions. In the best case, the complexity can be reduced from exponential down to just linear.
We use the pruning approach to solve a range of schedulability analysis problems. We first derive an exact schedulability test for sporadic real-time tasks, scheduled by Global Fixed Priority (GFP). Our test is faster and less memory consuming, compared to all previously known exact tests. We achieve such results by pruning the state space through employing such constraints as i) a sufficient schedulability condition, ii) the length bound for the longest release sequence to be considered, iii) critical job release instants, iv) an optimized clock transition between checked system states, as well as others. We also extend the test to continuous-time schedulers (e.g. an event-driven scheduler, which is opposed to a tick-driven scheduler), discarding the assimption of discrete time and integer task parameters, by employing linear programming methods combined with the search space pruning, instead of naive enumeration methods.
Another considered problem is the schedulability analysis of compositional multiprocessor real-time systems. Our solution is based on solving a set of mixed-integer non-convex optimization problems. Due to their high complexity, no existing solver could efficiently determine a solution. To make solving possible, we first prune the solution search space, exploring the theoretical insides of the scheduling problem, and then employ an adequate optimization solver over a reduced search space, so that it quickly finds an optimal solution. The resulted search space is so narrow, that approximate solvers perform almost as good as exact ones: in most cases an approximate solver finds a true global optimum, but significantly faster compared to an exact solver.All solutions have been implemented in C++ and Matlab environments, and they are publicly available.

University of Porto
- PhD degree in Electrical and Computer Engineering Research areas: computer science, multiprocessor scheduling, real-time systems Moscow Engineering Physics Institute (State University)
- Master’s degree in Computer Sciences Since February 2010
Polytechnic Institute of Porto (P.Porto) Research Centre in Real-Time and Embedded Computing Systems (CISTER) Researcher / Software engineer January 2006 – March 2010
European Organization for Nuclear Research (CERN) Project Associate in LHC Gas Control System (LHC GCS)