Giới hạn dưới cho việc tối thiểu hóa thời gian hoàn thành trực tuyến trên một số lượng nhỏ máy móc liên quan

Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997). On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM, 44, 486–504. Azar, Y. (1998). On-line load balancing. In A. Fiat & G. J. Woeginger (Eds.), Online algorithms: the state of the art (pp. 178–195). Berlin: Springer. Bar-Noy, A., Freund, A., & Naor, J. (2000). New algorithms for related machines with temporary jobs. Journal of Scheduling, 3, 259–272. Berman, P., Charikar, M., & Karpinski, M. (2000). On-line load balancing for related machines. Journal of Algorithms, 35, 108–121. Cai, S. Y., & Yang, Q. F. (2012). Online scheduling on three uniform machines. Discrete Applied Mathematics, 160(3), 291–302. Chen, B., van Vliet, A., & Woeginger, G. J. (1994). New lower and upper bounds for on-line scheduling. Operations Research Letters, 16, 221–230. Cho, Y., & Sahni, S. (1980). Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9, 91–103. Ebenlendr, T. (2011). Combinatorial algorithms for online problems: semi-online scheduling on related machines. Ph.D. Thesis, Charles University, Prague. Ebenlendr, T., & Sgall, J. (2012). A lower bound on deterministic online algorithms for scheduling on related machines without preemption. In Lecture notes in comput. sci.: Vol. 7164. Proc. 9th international workshop in approximation and online algorithms (WAOA 2011) (pp. 102–108). Berlin: Springer. Ebenlendr, T., Jawor, W., & Sgall, J. (2009). Preemptive online scheduling: optimal algorithms for all speeds. Algorithmica, 53, 504–522. Epstein, L., & Sgall, J. (2000). A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26, 17–22. Epstein, L., Noga, J., Seiden, S. S., Sgall, J., & Woeginger, G. J. (2001). Randomized on-line scheduling for two uniform machines. Journal of Scheduling, 4, 71–92. Faigle, U., Kern, W., & Turán, G. (1989). On the performance of online algorithms for partition problems. Acta Cybernetica, 9, 107–119. Fleischer, R., & Wahl, M. (2000). On-line scheduling revisited. Journal of Scheduling, 3, 343–353. Galambos, G., & Woeginger, G. J. (1993). An on-line scheduling heuristic with better worst case ratio than Graham’s list scheduling. SIAM Journal on Computing, 22, 349–355. Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 45, 1563–1581. Han, F., Tan, Z., & Yang, Y. (2011, to appear). On the optimality of list scheduling for online uniform machines scheduling. Optimization Letters. doi:10.1007/s11590-011-0335-x. Musitelli, A., & Nicoletti, J. M. (2011). Competitive ratio of list scheduling on uniform machines and randomized heuristics. Journal of Scheduling, 14, 89–101. Rudin, J. F. III (2001). Improved bound for the online scheduling problem. Ph.D. Thesis, The University of Texas at Dallas.