Genetic approach for real-time scheduling on multiprocessor systems

Real-time scheduling of concurrent tasks on multiprocessor systems is a complex job, which implies finding a feasible solution in a multi-dimensional space. In order to reduce the search time we propose a genetic approach for two important aspects of the scheduling problem: task allocation and deadline assignment. We combine a genetic search engine with a simulation tool in order to find a scheduling strategy that assures the fulfillment of all time restrictions. Our system model includes a wide range of multiprocessor systems, from parallel systems to network-based distributed ones and from independent task sets to chains of tasks organized as concurrent transactions. The paper gives details regarding the adaptation of genetic operators for the scheduling problem.