FANG Ming, Harbin Engineering University, Harbin, China
To overcome the disadvantages of existing algorithms in scheduling distributed real-time tasks, this paper proposes a post-scheduling optimization algorithm (PSO) based on a novel structure called Scheduled Clusters Tree. As the experiments shows, PSO can minimize the number of required processors without affecting the optimal scheduling length generated by duplication-based algorithms, e.g., TDS or OSA algorithm. The time complexity of PSO algorithm is O(d|V|2) when TDS is adopted, or O(d2|V|2) when OSA is adopted. Where |V| is the number of tasks and d is the maximum degree of tasks in the corresponding DAG.
Citation:
FANG Ming, YUAN You-guang, LIANG Hong-tao, "A Post-Scheduling Optimization Algorithm of Distributed Real-Time Tasks," pdcat, pp.1083-1086, Sixth International Conference on Parallel and Distributed Computing Applications and Technologies (PDCAT'05), 2005