New Hybrid Genetic Based Approach for Real-Time Scheduling of Multiprocessor Reconfigurable Embedded Systems

摘要

This paper deals with the problem of scheduling multiprocessor real-time tasks by a hybrid genetic based scheduling algorithm. We propose a new hybrid genetic based scheduling approach that automatically checks the systems feasibility after any reconfiguration scenario was applied on a multiprocessor embedded system. Indeed, if the system is unfeasible, the proposed approach operates directly in a highly dynamic and unpredictable environment and improves a rescheduling performance. This proposed approach which is based on a genetic algorithm (GA) combined with a tabu search (TS) algorithm is implemented which can find an optimized scheduling strategy to reschedule the embedded system after any system disturbance was happened. We mean by a system disturbance any automatic reconfiguration which is assumed to be applied at run-time: Addition-Removal of tasks or just modifications of their temporal parameters: WCET and/or deadlines. An example used as a benchmark is given, and the experimental results demonstrate the effectiveness of the proposed genetic based scheduling approach over others such as classical genetic algorithm approach.