%0 Journal Article
%T Bin-packing algorithms for periodic task scheduling<br>周期性任务调度的装箱算法
%A ZHU Zhi-lin
%A SHI Chen
%A HAN Jun-gang
%A CHEN Ping
%A <br>朱智林
%A 时晨
%A 韩俊刚
%A 陈平
%J 计算机应用
%D 2006
%I 
%X 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.
%K TTCAN<br>装箱问题
%K 周期性任务调度
%K 渐近性能比
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=831E194C147C78FAAFCC50BC7ADD1732&aid=58A0D07E6FCFA9D2&yid=37904DC365DD7266&vid=96C778EE049EE47D&iid=38B194292C032A66&sid=DC06EBDBAF4E06D3&eid=91F993CDA99CBE0B&journal_id=1001-9081&journal_name=计算机应用&referenced_num=4&reference_num=10