A Static Scheduling Algorithm Based on Global Task-Transferring

The task scheduling in a distributed real time system is known as an NP-complete problem. A typical heuristic algorithm, TDS, can generate optimal schedule in scheduling length under optimality condition. The TDS algorithm can not minimize the demanded processor number because it selects and schedules task nodes in a local area. In this paper, a global task-transferring (GTT) based scheduling algorithm is proposed as an advanced TDS algorithm. Compared with other existing scheduling schemes, including TDS, the GTT algorithm can minimize the processor number, improve speedup and efficiency obviously, and keep the optimality in scheduling length and optimality condition. The GTT algorithm has the time complexity of O(d|V|2) where |V| represents the number of tasks and d represents the maximum degree of tasks.