A Local Search Algorithm to Find a Scheduling Table for Real-Time Systems

作者：Hashimoto Hideki^*; Sugiyama Taichiro; Tanaka Yuma; Yagiura Mutsunori

来源：Journal of Advanced Mechanical Design Systems and Manufacturing, 2012, 6(5): 741-751.

DOI：10.1299/jamdsm.6.741

• Real-Time System
• Embedded System
• Response Time
• Local Search
• Scheduling Table

A real-time system receives input from the outside, processes it through a sequence of tasks and outputs the result to the outside. Each process corresponds to a sequence of tasks called path and the time from input to output is called response time. For each path, a response time must always be within a specified time. Our objective is to schedule tasks so that the time constraints for all paths are satisfied. In this paper, we adopt a scheduling method based on a scheduling table, which specifies a schedule of a finite time period and is used repeatedly to define the schedule of longer time periods. In order to calculate response times for a schedule efficiently, we introduce a concept called active path. In our algorithm, a scheduling table is searched by a local search. The neighborhood search is accelerated by using precedence relations that are introduced to preserve active paths of a scheduling table. Finally, we report computational results for sample instances from a company.

• 出版日期2012