A novel task scheduling approach for dependent non‐preemptive tasks using fuzzy logic

Abstract

Abstract Multiprocessor task scheduling problem is a pressing problem that affects systems' performance and is still being investigated by the researchers. Finding the optimal schedules is considered to be a computationally hard problem. Recently, researchers have used fuzzy logic in the field of task scheduling to achieve optimal performance, but this area of research is still not well investigated. In addition, there are various scheduling algorithms that used fuzzy logic but most of them are often performed on uniprocessor systems. This article presents a new proposed algorithm in which the priorities of the tasks are derived from the fuzzy logic and bottom level parameter. This approach is designed to find task schedules with optimal or sub‐optimal lengths in order to achieve high performance for a multiprocessor environment. With respect to the proposed algorithm, the precedence constraints between the non‐preemptive tasks and their execution times are known and described by a directed acyclic graph. The number of processors is fixed, the communication costs are negligible and the processors are homogeneous. The suggested technique is tested and compared with the Prototype Standard Task Graph Set.

Keywords

• computational complexity
• directed graphs
• fuzzy logic
• multiprocessing systems
• parallel algorithms
• processor scheduling