Adaptive Genetic Algorithm: Scheduling Hard Real-time Control Programs with Arbitrary Timing Constraints

In hard real-time systems, a timing fault may lead the environment to catastrophe. Thus, a real-time program must be executed in accordance with the timing constraints specified in the control program. Dynamic scheduling approach which has been dominant for real-time systems are unacceptable due to run-time scheduling overhead and unpredictable risks. In contrast, a static approach takes advantage of thorough search for scheduling, no scheduling overhead, and guaranteed execution of compiled program. However, finding an optimal schedule for real-time tasks with precedence is known as NPhard problem, demanding a heuristic approach. In this paper, we propose an adaptive genetic approach to find a valid schedule. Adaptive genetic approach implies that the algorithm relies on not only stochastic behavior of the search but also deterministic behavior based on program structure. This paper includes new computation model with arbitrary before and after constraints, description of m..