An algorithm for scheduling parallel processors

Abstract

This paper deals with optimal scheduling of jobs on identical parallel processors. The paper develops an algorithm for determining the optimal schedule and gives a proof of the algorithm. The criterion used is that of minimizing the total cost for processing all jobs when the jobs are assigned non-decreasing waiting costs which are non-linear. Extension of the algorithm for jobs with due dates is also given. Computational results are given which indicate the effectiveness of the algorithm as compared to complete enumeration.