On static scheduling of tasks in real time multiprocessor systems : an improved ga-based approach

Abstract EN

Task execution deadline time in real-time systems is a critical constraint.

Every task should have a maximum computational time (MCT) that is needed before reaching a given deadline time (DL).

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 Priority Genetic Algorithm (PGA) is introduced and experimentally evaluated against already proposed algorithms in literature.

I', or \ sjus“ like the GA algorithm introduced in Abraham et al (2008).

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 task.

visibility compared with Genetic (G) and Earliest Deadline First (EDF) algorithms.

We have also found that this improvement becomes more and more effective with the increase of problem size.