Permutation-based particle swarm algorithm for tasks scheduling in heterogeneous systems with communication delays

A distributed heterogeneous system consists of a suite of processors or machines with different processing capacities. It can be performance-to-cost efficient to meet the diverse computation requirements if properly deployed. Task scheduling is a crucial issue to improve the efficiency of this architecture. In this paper, we incorporate a miscellaneous population-based search technique, Particle Swarm Optimization (PSO), with list scheduling and develop an alternative PSO algorithm for multiprocessor tasks scheduling. The framework of the hybrid PSO algorithm for the multiprocessor scheduling is developed according to the permutation-based solution representation to find optimal task-machine pairs. The merit of the hybrid method is to keep improving the potential solution continuously through learning experience from the searching knowledge of one particle itself or the best of all particles in the swarm in the interest of minimizing the scheduling length. We also implement a few assigning rules to select target machine with different processing speeds. The proposed model considers arbitrary networks in more realistic environments and the scheduling method takes communication delays into account. The results show that the proposed algorithm is able to find good quality schedules in reasonable time and has some advantages over other algorithms.