Scheduling independent Tasks on homogenous multiprocessors using Bees Algorithm


Abstract in English

Scheduling tasks on multiprocessors is considered one of the most important issues studied to make processors operate without inertia (idleness) and thus to reduce the total time of completion or makespan. This increased interest in studying scheduling and its algorithms, especially in multiprocessor systems that need to arrange the tasks to been optimally implemented. In this research, we study the static scheduling issue for the independent tasks on a homogenous multiprocessor system. In addition, we develop an algorithm based on Bees Colony Optimization to solve the scheduling Problem. Thereafter, our algorithm is compared with a previous one inspired also by the bees behavior for the same purpose, and the optimal solution for the displayed scheduling Problem. The aim of the algorithm is to find an acceptable solution with the best time through Bees Colony's algorithm. To evaluate our reach, we Study the effect of increasing the number of tasks when processors numbers are constant, and the impact of increasing the number of processors for a number of tasks on the stability of the presented algorithm. Our algorithm has shown the ability to obtain optimal value for the objective function in terms of scheduling tests for small and medium size. Our results shown that the imposed algorithm gives the best solution for the scheduling problem, in most cases, and improves the traditional BCO algorithm.

References used

G. BENI, 1988. “The concept of cellular robotic system,” in Proc. of the IEEE International Symposium on Intelligent Control, IEEE Computer Society Press, Los Alamitos, CA , pp. 57–62
G. BENI, AND J. WANG, 1989. “Swarm intelligence,” in Proc. of the Seventh Annual Meeting of the Robotics Society of Japan, RSJ Press, Tokyo, pp. 425–428
G. BENI, AND S. HACKWOOD, 1992. “Stationary waves in cyclic swarms,” in: Proc. of the International Symposium on Intelligent Control, IEEE Computer Society Press, Los Alamitos, CA, pp. 234–242
E. BONABEAU, M. DORIGO, AND G. THERAULAZ, 1997. Swarm intelligence. Oxford University Press, Oxford
S. CAMAZINE, AND J. SNEYD, 1991. “A model of collective nectar source by honey bees: self-organization through simple rules,” Journal of Theoretical Biology, vol. 149, pp. 547- 571

Download