Preemptive scheduling on a small number of hierarchical machines

Aspnes, 1997, On-line load balancing with applications to machine scheduling and virtual circuit routing, J. ACM, 44, 486, 10.1145/258128.258201 Azar, 1995, The competitiveness of on-line assignments, J. Algorithms, 18, 221, 10.1006/jagm.1995.1008 Bar-Noy, 2001, On-line load balancing in a hierarchical server topology, SIAM J. Comput., 31, 527, 10.1137/S0097539798346135 Berman, 2000, On-line load balancing for related machines, J. Algorithms, 35, 108, 10.1006/jagm.1999.1070 Chen, 1994, Lower bounds for randomized online scheduling, Inform. Process. Lett., 51, 219, 10.1016/0020-0190(94)00110-3 Chen, 1995, An optimal algorithm for preemptive on-line scheduling, Oper. Res. Lett., 18, 127, 10.1016/0167-6377(95)00039-9 Crescenzi, 2004, On-line algorithms for the channel assignment problem in cellular networks, Discrete Appl. Math., 137, 237, 10.1016/S0166-218X(03)00341-X T. Ebenlendr, W. Jawor, J. Sgall, Preemptive online scheduling: optimal algorithms for all speeds, in: Proceedings of the 14th Annual European Symposium on Algorithms (ESA2006), 2006, pp. 327–339. Epstein, 2001, Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios, Oper. Res. Lett., 29, 93, 10.1016/S0167-6377(01)00085-2 Epstein, 2001, Randomized online scheduling on two uniform machines, J. Scheduling, 4, 71, 10.1002/jos.60 Epstein, 2000, A lower bound for on-line scheduling on uniformly related machines, Oper. Res. Lett., 26, 17, 10.1016/S0167-6377(99)00062-0 Graham, 1966, Bounds for certain multiprocessing anomalies, Bell Syst. Techn. J., 45, 1563, 10.1002/j.1538-7305.1966.tb01709.x Jiang, 2006, Optimal online algorithms for scheduling on two identical machines under a grade of service, J. Zhejiang Univ. Sci. A, 7, 309, 10.1631/jzus.2006.A0309 Park, 2006, Online and semi-online scheduling of two machines under a grade of service provision, Oper. Res. Lett., 34, 692, 10.1016/j.orl.2005.11.004 Seiden, 2001, Preemptive multiprocessor scheduling with rejection, Theor. Comput. Sci., 262, 437, 10.1016/S0304-3975(00)00288-7 Sgall, 1997, A lower bound for randomized on-line multiprocessor scheduling, Inform. Process. Lett., 63, 51, 10.1016/S0020-0190(97)00093-8 Wen, 1998, Preemptive on-line scheduling for two uniform processors, Oper. Res. Lett., 23, 113, 10.1016/S0167-6377(98)00032-7 A.C.C. Yao, Probabilistic computations: towards a unified measure of complexity, in: Proceedings of 18th Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 222–227, 1977.