Optimal Scheduling of Tasks on Identical Parallel Processors

Abstract

We consider the classical problem of scheduling n tasks with given processing time on m identical parallel processors so as to minimize the maximum completion time of a task. We introduce lower bounds, approximation algorithms and a branch-and-bound procedure for the exact solution of the problem. Extensive computational results show that, in many cases, large-size instances of the problem can be solved exactly. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.