Comparative Analysis of Job Scheduling Algorithms in Parallel and Distributed Computing Environments

Abstract

Due to an unprecedented increase in the number of computing resources in different organizations, effective job scheduling algorithms are required for efficient resource utilization. Job scheduling in considered as NP hard problem in parallel and distributed computing environments such as cluster, grid and clouds. Metaheuristics such as Genetic Algorithms, Ant Colony Optimization, Artificial Bee Colony, Cuckoo Search, Firefly Algorithm, Bat Algorithm etc. are used by researchers to get near optimal solutions to job scheduling problems. These metaheuristic algorithms are used to schedule different types of jobs such as BSP, Workflow and DAG, Independent tasks and Bag-of-Tasks. This paper is an attempt to provide comprehensive review of popular nature-inspired metaheuristic techniques which are used to schedule different categories of jobs to achieve certain performance objectives.

Keywords: scheduling, metaheuristics, multi-criteria, metrics, BSP, workflow, independent tasks, bag-of-tasks