On-line scheduling revisited

Abstract

We present a new on-line algorithm, MR, for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m⩾64. For m→∞ its competitive ratio approaches 1+\sqrt{(1+1{\rm n} 2)/2}<1.9201. Copyright 2000 © John Wiley & Sons, Ltd.