Two Post-Scheduling Optimization Algorithms for Distributed Real-Time Tasks Based on Scheduled Cluster Tree

To overcome the disadvantages of the existing task duplication-based algorithms, this paper discusses the scheduling objectives of distributed real-time tasks, presents a novel structure called scheduled cluster tree, and proposes a general optimization method for various task duplication-based algorithms. According to the result of experiments, PSO_I and PSO_II are both general algorithms that improve the schedules generated by various task duplication-based algorithms. PSO_I aims to optimize the schedules in minimizing the number of required processors without affecting the optimal scheduling length acquired. PSO_II aims to increase the utilization of processors at the acceptable expense of the scheduling length (i.e., in the range of deadline) besides minimizing the number of required processors. The time complexities of both methods match approximately that of the typical task duplication-based algorithms, e.g., the task duplication based scheduling algorithm and the optimal scheduling algorithm based on task duplication