Randomized on-line scheduling on two uniform machines

We study the problem of on-line scheduling on two uniform machines with spe eds 1 and s greater than or equal to 1. A phi approximate to 1.61803 compet itive deterministic algorithm was already known. We present the first rando mized results for this problem: We show that randomization does not help fo r speeds s greater than or equal to 2, but does help for all s < 2. We pres ent a simple memoryless randomized algorithm with competitive ratio (4 - s) (1 + s)/4 <less than or equal to> 1.56250. We analyse other randomized algo rithms that demonstrate that the randomized competitive ratio is at most 1. 52778 for any s. These algorithms are barely random, i.e. they use only a c onstant number of random bits. Finally, we present a 1 + s/(s(2) + s + 1) c ompetitive deterministic algorithm for the preemptive version of this probl em. For any s, it is best possible even among randomized preemptive algorit hms. Copyright (C) 2001 John Wiley & Sons, Ltd.