An Imperialist Competitve Algorithm for solving the Multi Processor Scheduling Problem

Scheduling is a key problem in multi-processor systems in order to benefit from the large computing capacity of such systems and is an NP-complete problem. In this paper, we propose a meta heuristic technique, namely the Imperialist Competitive Algorithm (ICA), for homogeneous multiprocessor scheduling problem (MPSP).ICA is a population-based search algorithm based on the simulation of the socio-political process of imperialism and imperialistic competition. Imperial compete in problem search space to find optimal or near-optimal solutions. The scheduler aims at minimizing makespan, which is the time when finishes the latest job. Also in this paper, a simple method proposed to calculate the relative power of the empires in imperialist competitive algorithm, which calculation is less than the original method and runs faster. Experimental Evaluation shows that the proposed method is efficient of Genetic Algorithm (GA) approach for this problem.

کلیدواژه ها:

colonial ، imperialist competitive algorithm ، multiprocessor scheduling problem (MPSP) ، scheduling