A job allocation algorithm for parallel processors

Abstract

We are given a nite set of jobs of equal processing times with readiness times and tails and a set of identical processors. The aim is to schedule the given set of jobs on the given set of processors to minimize the total processing time (or makespan). An algorithm for that problem with the time complexity O(n logn) was proposed earlier in [10]. This algorithm improves the running time of the previously known best algorithm [9] under the assumption that the tails of all jobs are bounded by some constant. In this paper we show that an algorithm based on the ideas of the algorithm from [10] can be constructed in which the above restriction is removed.