On Static Scheduling of Tasks in Real Time Multiprocessor Systems: An Improved GA-Based Approach

Task execution Deadline Time (DL) in real-time systems is a critical constraint. Every task should have a Maximum Computational Time (MCT) that is needed before reaching a given DL time. Scheduling jobs in real-time systems is thus a nondeterministic polynomial NP problem. Three algorithms can be found in literature to solve these problems in a multi processor environment; are the Earliest Deadline First (EDF), Genetic Algorithms (GA), Priority Genetic Algorithms (PGA). In this research, the PGA is introduced and experimentally evaluated against already proposed algorithms in literature. It works just like the GA algorithm introduced in Abraham et al. [1]. However, we do not only consider the DL in sorting the tasks in the first population, but rather, we also include the MCT of individuals in the population to define the priority level of these tasks. We have found that the proposed algorithm has a better average total system utilization, total system tasks visibility compared with Genetic (G) and EDF algorithms. We have also found that this improvement becomes more and more effective with the increase of problem size.