周期性任务调度的装箱算法

Bin-packing algorithms for periodic task scheduling

针对基于时间触发的CAN控制系统,给出了确定周期性任务表中的基本周期的两种策略,提出了构造周期性任务调度表的下次适应、降序下次适应、最佳适应和降序最佳适应四种算法,分析了这四种不同算法的时间复杂度和最坏渐近性能比,最后对不同规模下的四种算法进行了仿真比较,结果表明文中给出的四种算法效果均优于经典的一维装箱算法。

As the extension of off-line bin-packing problem, periodic task scheduling has many important applications in real-time distributed systems. For time triggered CAN control systems, two strategies to determine basic cycle（BC） of TTCAN were presented. Next-fit algorithm, next-fit deereaming algorithm, best-fit algorithm and best-fit decreaming algorithm were proposed to construct periodic task scheduling tables. Time complexity and worst-case asymptotic performance ratio of these algorithms were analyzed. Experiment results show that the four algorithms have the advantage over the typical one-dimensional bin-packing algorithm.