A Problem-Specific Genetic Algorithm for Multiprocessor Real-Time Task Scheduling

Real-time task scheduling for multiprocessor systems is generally a NP-complete problem and thus genetic algorithms (GAs) are extensively used. However, since GAs aim to be one kind of universal algorithm across a variety of problem types, they hardly use problem-specific search techniques which might help speed up the search process or lead to a better solution under certain scenarios. That partly prevents GAs from performing more effectively and efficiently. To overcome this, a problem-specific genetic algorithm is proposed to handle multiprocessor real-time task scheduling in this paper. The simulation results show that the performance of the GA are greatly improved with the assistance of certain problem-specific knowledge.