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 are presented. Next-fit algorithm, next-fit decreasing algorithm, best-fit algorithm and best-fit decreasing algorithm are proposed to construct periodic task scheduling tables. Time complexity and worst-case asymptotic performance ratio of these algorithms are analyzed, and experiment results are compared in different problem size.
展开▼