Task Scheduling in Heterogeneous Computing Systems Using Swarm Intelligence
S. Sarathambekai, K. Umamaheswari · 2020
Heterogeneous computing system has become necessary in real time for providing a massive amount of computational resources to execute large-scale complex applications. An efficient scheduling policy is needed to allocate the available resources to the users in the distributed heterogeneous environment. Task scheduling (TS) problem is one of the challenging issues in the distributed environment. Heuristics/metaheuristic methods have been used to solve such problems in order to obtain a near-optimal solution within a finite duration. Particle swarm optimization (PSO) is a Swarm Intelligence (SI) based metaheuristic algorithm, does not have any evolutionary operators like selection, crossover, and mutation, and so is computationally inexpensive when compared to other evolutionary algorithms. In general, SI-based algorithms are designed to address the continuous optimization problem. TS is one of the discrete optimization problems because of using a discrete decision variable, namely the task numbers or processor numbers. However, the classical PSO cannot be used directly in the TS problem because their positions happen to be continuous values. Therefore, a Discrete PSO (DPSO) algorithm is introduced, in which the particles can update their positions in a discrete domain directly. This feature in DPSO saves a considerable amount of computational time. In DPSO, the neighborhood topological structure may significantly contribute to the performance improvement of the algorithm. This chapter emphasizes the significance of neighborhood structure in DPSO algorithm for meta-tasks scheduling problem in heterogeneous computing systems. The details of the various well-known neighborhood structures such as Mesh, Star, Ring, Von Neumann (VN), and Binary Tree are discussed with illustrative examples. The structure of these topological models is constant and hence they may trap in the local optima. Therefore, a dynamic neighborhood structure, namely the Binary Heap Tree (BHT) model for the particle communication, has been presented, with a detailed procedure. The inclusion of the dynamic BHT model in DPSO permits the particles to search the solutions in new areas of the search space. This increases the algorithm's exploration and reduces the local optima problem.