The authors consider the following scheduling problem. There are m parallel machines and n independent jobs. Each job is to be assigned to one of the machines. The processing of job j on machine i requires time pij. The objective is to find a schedule that minimizes the makespan. The present main result is a polynomial algorithm which constructs a schedule that is guaranteed to be no longer than twice the optimum. The authors also present a polynomial approximation scheme for the case that the number of machines is fixed. Both approximation results are corollaries of a theorem about the relationship of a class of integer programming problems and their linear programming relaxations. In particular, the authors give a polynomial method to round the fractional extreme points of the linear program to integral points that nearly satisfy the constraints. In contrast to the present main result, they prove that no polynomial algorithm can achieve a worst-case ratio less than 3/2 unless P=NP. The authors finally obtain a complexity classification for all special cases with a fixed number of processing times.
