Bin-packing Algorithms for Periodic Task Scheduling

Author

Zhu, Zhilin ; Sui, Jinxue ; Yang, Li

Author_Institution

Sch. of Inf. & Electron. Eng., Shandong Inst. of Bus. & Technol., Yantai, China

Volume

2

fYear

2010

fDate

14-15 Aug. 2010

Firstpage

207

Lastpage

210

Abstract

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.

Keywords

bin packing; computational complexity; controller area networks; scheduling; best-fit algorithm; best-fit decreasing algorithm; bin-packing algorithms; controller area network; next-fit algorithm; next-fit decreasing algorithm; periodic task scheduling; realtime distributed systems; time complexity; time triggered CAN control systems; worst-case asymptotic performance ratio; Algorithm design and analysis; Approximation algorithms; Complexity theory; Control systems; Data communication; Real time systems; Scheduling; Asymptotic performance ratio; Bin-packing problem; Periodic task scheduling;

fLanguage

English

Publisher

ieee

Conference_Titel

Information Engineering (ICIE), 2010 WASE International Conference on

Conference_Location

Beidaihe, Hebei

Print_ISBN

978-1-4244-7506-3

Electronic_ISBN

978-1-4244-7507-0

Type

conf

DOI

10.1109/ICIE.2010.145

Filename

5571344