We prove that any randomized algorithm for on-line scheduling jobs on m identical parallel machines must have a worst case ratio at least mm/(mm-(m-1)m) for every m, which tends to e/(e-1) ˜ 1.58 as m¿8. This answers a question posed in a recent paper by Bartal, Fiat, Karloff and Vohra.
Chen, B., Vliet, van, A., & Woeginger, G. J. (1994). A lower bound for randomized on-line scheduling algorithms. Information Processing Letters, 51(5), 219-222. https://doi.org/10.1016/0020-0190(94)00110-3