Efficient Scheduling Algorithms for Multicore Cyclic Executives With Precedence and Exclusion Relations

ABSTRACT Cyclic executives (CEs) offer the advantage of ensuring complete determinism with minimal runtime overhead, often making them the preferred choice for safety‐critical real‐time systems. However, generating CEs for multicore processors while addressing task precedence and exclusion relations presents significant challenges. In this paper, unlike previous work, we tackle these challenges by proposing integer linear programming (ILP) models to generate optimal preemptive and non‐preemptive CEs, considering both partitioned and global work allocation schemes. Additionally, we introduce a local search‐based heuristic to efficiently produce approximate solutions. Our methods are evaluated on both synthetic and benchmark instances from the literature, encompassing thousands of tasks and complex inter‐task dependencies, and include a direct comparison with a state‐of‐the‐art approximation method. The experimental results highlight the effectiveness of the proposed approaches in generating optimal or near‐optimal CEs for large‐scale task sets.