We consider randomized algorithms for on-line scheduling on identical machines. For two machines, a randomized algorithm achieving a competitive ratio of 4/3 was found by Bartal et al. Seiden has presented a randomized algorithm which achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m=3,4,5,6,7, respectively. A barely random algorithm is one which is a distribution over a constant number of deterministic strategies. The algorithms of Bartal et al. and Seiden are not barely random – in fact, these algorithms potentially make a random choice for each job scheduled. We present the first barely random on-line scheduling algorithms. In addition, our algorithms use less space and time than the previous algorithms, asymptotically.
