Efficient algorithms for job scheduling in parallel systems

Abstract

In this study, the job scheduling problem in parallel systems is addressed. It can be stated as the problem of allocating a set of jobs or tasks to a set of parallel processors or machines to minimize the overall execution time. It has been shown that, it is almost impossible to develop exact optimal algorithms to solve this problem, as it is categorized as a NP-hard problem. Therefore, it has been necessary to develop efficient algorithms which will lead to near optimal solutions and that can solve real world problem instances. We consider a mathematical treatment of the job scheduling problem in parallel systems.

Several approximation algorithms are developed in this study. Minimizing of the makespan is the objective function considered in the study. First, more efficient single thread algorithms for the parallel job scheduling problem are developed. Then, the concept of multi-threading is used to propose several new more efficient algorithms based on the concepts of gang scheduling and backfilling, which are applicable to large scale parallel systems.

In order to estimate the quality of solutions obtained, lower bounds and percentage gaps are derived. Mainly, small and medium scale test problems are used in this study, with a few large scale problems as well. However, it is shown that the results can be applied to large scale problem instances, in general. A method to determine the proximity of solutions to the relevant optimal solutions using statistical techniques is also developed. Performance evaluation of the algorithms is presented in detail. It is shown that our solutions are extremely close to the relevant optimal solutions. All the proposed algorithms are polynomial time algorithms.

The random nature of the job completion time is also considered. When the number of jobs and processors are fixed, there can be an infinite number of ways of varying individual job completion times for a given total job execution time for all the jobs. Using more than twenty thousand data sets, performance of algorithms are compared. It is shown that, the performance level of the algorithms does not change even if the random nature of job completion times were considered.