Bin-packing algorithms for periodic task scheduling
周期性任务调度的装箱算法

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 decreaming 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.