An empirical study of permutational genetic crossover and mutation operators on the fixed priority assignment in distributed real-time systems

The assignment of fixed priorities to tasks and messages in distributed real-time systems is known to be an NP-hard problem, so there is no optimal method to accomplish it in polynomial time. Several generic search and optimization methods have been proposed in the literature for the priority-based scheduling of distributed real-time systems. The permutational genetic algorithm is one of those techniques that has shown a notable ability to solve this problem. The success of a genetic algorithm is greatly influenced by the used crossover and mutation operators, whose performance may vary between different problems. In this paper we make an introduction of some crossover and mutation operators for permutational genetic algorithms and make an experimental analysis of their performance in the assignment of fixed priorities to tasks and messages in distributed real-time systems.