Task Allocation In A Multiprocessor System Using Fuzzy Logic

Abstract

Task scheduling for multiprocessors is a job-sequencing problem generally classified as NP-complete or NP-hard. Optimal solutions to the problem using some well-known algorithms can only be obtained in some restricted cases. In most cases,however, this is not possible. Therefore, near-optimal solutions to the problem have been developed using heuristics. This paper proposes a new heuristic using fuzzy logic to achieve near optimum load balancing for the task allocation problem in a multiprocessor system. Task allocation is a restricted case of task scheduling where the tasks have no precedence relations with others and the priority order of execution is ignored. The tasks are assumed to be non-preemptable, have no execution deadlines and have no interprocessor communication. It is possible to·apply the fuzzy concepts since the problems involved are difficult to model mathematically. Much of its power of fuzzy logic is derived from its ability to draw conclusion and generate responses based on incomplete and imprecise informations.