ABSTRACT
Multiprocessor scheduling is one of the most challenging problems in parallel and distributed computing [1]. It is known to be NP-complete in its general form [2]. Researchers have studied restricted forms of the problem by constraining either a parallel program model or a multiprocessor model. However, these special cases do not fully represent real-world systems. To solve the scheduling problem in the general case, a number of heuristics based on different mathematical platforms and metaheuristics based on mechanisms observed in nature, have been introduced. The commonly known heuristics are list scheduling, critical path, or clustering [3,4]. Recently metaheuristics such as simulated annealing (SA), genetic algorithms (GAs), ant colonies, tabu search (TS), or neural networks have been successfully applied [5,6].
