A novel Task Scheduling in Multiprocessor Systems with Genetic Algorithm by using Elitism stepping method

Abstract

Task scheduling is essential for the suitable operation of multiprocessor systems. The aim of task scheduling is to determine an assignment of tasks to processors for shortening the length of schedules. The problem of task scheduling on multiprocessor systems is known to be NP-complete in general. Solving this problem using by conventional techniques needs reasonable amounts of time. Therefore, many heuristic techniques were introduced for solving it. This paper presents a new heuristic algorithm for task scheduling, based on evolutionary method which embeds a new fast technique named Elitism Stepping into Genetic Algorithm (GA). By comparing the proposed algorithm with an existing GA-based algorithm, it is found that the computation time of the new algorithm to find a sub-optimal schedule is decreased; however, the length of schedule or the finish time is decreased too.