On randomized online scheduling
Susanne Albers · 2002
ABSTRACT We study one of the most basic problems in online scheduling. A sequence of jobs has to be scheduled on m identical parallel machines so as to minimize the makespan. Whenever a new job arrives, its processing time is known in advance. The job has to be scheduled immediately on one of the machines without knowledge of any future jobs. In the sixties Graham presented the famous List scheduling algorithm which is (2 \\Gamma 1