Parallel swarm-based algorithms for scheduling independent tasks

Article type: Research Article

Authors: Dietze, Robert^* | Kränert, Maximilian

Affiliations: Chemnitz University of Technology, Chemnitz, Germany

Correspondence: [*] Corresponding author: Robert Dietze, Chemnitz University of Technology, Chemnitz, Germany. E-mail: robert.dietze@cs.tu-chemnitz.de.

Abstract: Task scheduling is crucial for achieving high performance in parallel computing. Since task scheduling is NP-hard, the efficient assignment of tasks to compute resources remains an issue. Across the literature, several algorithms have been proposed to solve different scheduling problems. One group of promising approaches in this field is formed by swarm-based algorithms which have a potential to benefit from a parallel execution. Common swarm-based algorithms are Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO). In this article, we propose two new scheduling methods based on parallel ACO, PSO and, Hill Climbing, respectively. These algorithms are used to solve the problem of scheduling independent tasks onto heterogeneous multicore platforms. The results of performance measuements demonstrate the improvements on the makespan and the scheduling time achieved by the parallel variants.

Keywords: Task scheduling, Ant Colony Optimization, Particle Swarm Optimization, Hill Climbing, parallel metaheuristics

DOI: 10.3233/HIS-230006

Journal: International Journal of Hybrid Intelligent Systems, vol. 19, no. 1,2, pp. 79-93, 2023