Bee colony optimization for scheduling independent tasks to identical processors

Abstract

The static scheduling of independent tasks on homogeneous multiprocessor systems is studied in this paper. This problem is treated by the Bee Colony Optimization (BCO) meta-heuristic. The BCO algorithm belongs to the class of stochastic swarm optimization methods inspired by the foraging habits of bees in nature. To investigate the performance of the proposed method extensive numerical experiments are performed. Our BCO algorithm is able to obtain the optimal value of the objective function in the majority of test examples known from literature. The deviation of non-optimal solutions from the optimal ones in our test examples is at most 2%. The CPU times required to find the best solutions by BCO are significantly smaller than the corresponding times required by the CPLEX optimization solver. Moreover, our BCO is competitive with state-of-the-art methods for similar problems, with respect to both solution quality and running time. The stability of BCO is examined through multiple executions and it is shown that solution deviation is less than 1%.