Abstract:
To address the multiprocessor task scheduling problem in real-time and intelligent integrated systems, this paper proposes two heuristic list scheduling algorithms: TB-LST and its improved variant TB-PLST. Both algorithms fully exploit the periodic characteristics of tasks to improve scheduling performance and consist of three phases. In the phase of adding time nodes, TB-LST and TB-PLST introduce time nodes to convert the arrival time attributes into dependency constraints between tasks. In the priority calculation phase, to rationally utilize predecessor tasks
' information, TB-LST employs the downward rank while TB-PLST adopts the average reverse optimistic cost as task priorities. In the processor selection phase, TB-LST uses the Latest Start Time (LST) as the decision criterion for processor selection. Building upon TB-LST, TB-PLST introduces Reverse Optimistic Cost Table (ROCT) and employs a greedy strategy to minimize the optimistic makespan of the task set. Complexity analysis demonstrates that the time complexities of the two proposed algorithms are comparable to those of state-of-the-art algorithms in the same category. Experimental results on both randomly generated graphs and real-world application graphs demonstrate that TB-LST and TB-PLST outperform mainstream list scheduling algorithms, including IPPTS, HEFT, CPOP, and PEFT, in terms of makespan, speedup ratio, and the frequency of yielding superior schedules.