New algorithms for an ancient scheduling problem

Abstract

We consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on the m machines so as to minimize the make span, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the m machines.