Projects per year
Abstract
Harmonic periods have wide applicability in industrial realtime systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. This property decreases the jitters which happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic. First, we assume that an interval is determined a priori for each task from which its period can be selected. The goal is to assign a (harmonic) period to each task such that the total system utilization is maximized while the task set remains feasible. We show that this problem is (at least) weakly NPhard. This is shown by reducing the NPcomplete number partitioning problem to the mentioned harmonic period assignment problem. Afterwards, we consider a variant of the problem in which the periods are not restricted to a special interval and the objective is to minimize the total weighted sum of the periods with the same feasibility constraint. We present two approximation algorithms for the second problem and show that the maximum error of these algorithms is bounded by a factor of 2. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.
Original language  English 

Title of host publication  Proceedings of the 24rd International Conference on Real Time and Networks Systems 
Publisher  Association for Computing Machinery (ACM) 
Pages  171180 
Number of pages  10 
ISBN (Electronic)  9781450347877 
DOIs  
Publication status  Published  2016 Oct 20 
Event  International Conference on RealTime Networks and Systems  Brest, France Duration: 2016 Oct 19 → 2016 Oct 21 Conference number: 24 http://rtns16.univbrest.fr 
Conference
Conference  International Conference on RealTime Networks and Systems 

Abbreviated title  RTNS 
Country/Territory  France 
City  Brest 
Period  2016/10/19 → 2016/10/21 
Internet address 
Subject classification (UKÄ)
 Control Engineering
Fingerprint
Dive into the research topics of 'On the Problem of Finding Optimal Harmonic Periods'. Together they form a unique fingerprint.Projects
 2 Finished

ELLIIT LU P02: CoDesign of Robust and Secure Networked Embedded Control Systems
Cervin, A., Årzén, K., Maggio, M., Vreman, N., Xu, Y., Bini, E., Nayak Seetanadi, G., Thelander Andrén, M., Pazzaglia, P., Peng, Z., Eles, P., Mahfouzi, R., Samii, S. & Aminifar, A.
2010/01/01 → 2020/01/31
Project: Research

Codesign of Networked Embedded Control Systems
Cervin, A., Xu, Y. & Årzén, K.
2010/01/01 → 2017/12/31
Project: Research
Prizes

Best Paper Award  RTNS 2016
Mohaqeqi, Morteza (Recipient), Nasri, Mitra (Recipient), Xu, Yang (Recipient), Cervin, Anton (Recipient) & Årzén, KarlErik (Recipient), 2016 Oct 20
Prize: Prize (including medals and awards)