A Cooperative Coevolutionary Approach to Designing Acceptance Tests for Jobs With Weakly Hard Real- Time Constraints
Karla Salamun, Hrvoje Džapo · 2024
Some real-time applications, including control sys-tems, communication systems, and multimedia systems, allow the relaxation of hard real-time constraints in the sense of tolerating deadline violations under certain conditions. The conditions that specify the ratio and distribution of tolerable deadline violations are defined through the weakly hard real-time constraints, and real-time systems that implement these constraints are referred to as weakly hard real-time systems. The majority of the existing approaches for scheduling tasks with weakly hard real-time constraints rely on classifying task instances, i.e., jobs, as either mandatory or optional (skippable), and provide a mechanism for ensuring timely completion of mandatory jobs, while aiming to maximize the number of timely completed optional jobs. However, few approaches implement online acceptance tests for optional jobs which ensure that jobs that are unable to be completed before their respective deadline are not accepted into the system. The existing acceptance tests for optional jobs have high computational complexity with respect to the number of tasks and are therefore not suitable for implementation on real-time computing platforms with limited resources. In this research, we develop a scheduling approach that maximizes the number of completed jobs and implements computationally efficient acceptance tests that ensure early rejection of jobs that cannot be completed before their deadline. This is achieved through a genetic programming approach with cooperative coevolution. Our approach uses two scheduling heuristics: a heuristic for dynamic job priority assignment, and a heuristic for evaluating acceptance for newly activated jobs. The results show that the proposed approach achieves comparable performance to state-of-the-art algorithms in terms of service quality, but with significantly lower computational overhead. Unlike the state-of-the-art scheduling algorithms, the scheduling heuristics generated by the proposed approach are suitable for implementation in real-time computing platforms due to their low computational complexity.