Optimal and online preemptive scheduling on uniformly related machines
Tóm tắt
We consider the problem of preemptive scheduling on uniformly related machines. We present a semi-online algorithm which, if the optimal makespan is given in advance, produces an optimal schedule. Using the standard doubling technique, this yields a 4-competitive deterministic and an e≈2.71-competitive randomized online algorithm. In addition, it matches the performance of the previously known algorithms for the offline case, with a considerably simpler proof. Finally, we study the performance of greedy heuristics for the same problem.
Tài liệu tham khảo
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 ACM, 44, 486–504.
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.
Chen, B., van Vliet, A., & Woeginger, G. J. (1995). An optimal algorithm for preemptive on-line scheduling. Operations Research Letters, 18, 127–131.
Cho, Y., & Sahni, S. (1980). Bounds for list schedules on uniform processors. SIAM Journal on Computing, 9, 91–103.
Cormen, T., Leiserson, C., & Rivest, R. (1990). Introduction to algorithms. New York: McGraw-Hill.
Dobson, G. (1984). Scheduling independent tasks on uniform processors. SIAM Journal on Computing, 13, 705–716.
Ebenlendr, T., Jawor, W., & Sgall, J. (2008). Preemptive online scheduling: Optimal algorithms for all speeds. Algorithmica, 53, 504–522.
Ebenlendr, T., & Sgall, J. (2004). Optimal and online preemptive scheduling on uniformly related machines. In Lecture notes in comput. sci.: Vol. 2996. Proc. 21st symp. on theoretical aspects of computer science (STACS) (pp. 199–210). Berlin: Springer.
Epstein, L. (2001). Optimal preemptive scheduling on uniform processors with non-decreasing speed ratios. Operations Research Letters, 29, 93–98.
Epstein, L. (2003). Bin stretching revisited. Acta Informatica, 39, 97–117.
Epstein, L., & Favrholdt, L. M. (2002). Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Operations Research Letters, 30, 269–275.
Epstein, L., Noga, J., Seiden, S. S., Sgall, J., & Woeginger, G. J. (2001). Randomized on-line scheduling for two related machines. Journal of Scheduling, 4, 71–92.
Epstein, L., & Sgall, J. (2000). A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters, 26(1), 17–22.
Friesen, D. K. (1987). Tighter bounds for LPT scheduling on uniform processors. SIAM Journal on Computing, 16, 554–560.
Gonzales, T. F., & Sahni, S. (1978). Preemptive scheduling of uniform processor systems. Journal of ACM, 25, 92–101.
Horwath, E., Lam, E. C., & Sethi, R. (1977). A level algorithm for preemptive scheduling. Journal of ACM, 24, 32–43.
Kovács, A. (2007). New approximation bounds for LPT scheduling. Algorithmica, to appear.
Mireault, P., Orlin, J. B., & Vohra, R. V. (1997). A parametric worst case analysis of the LPT heuristic for two uniform machines. Operations Research, 45, 116–125.
Shachnai, H., Tamir, T., & Woeginger, G. J. (2005). Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica, 42, 309–334.
Shmoys, D. B., Wein, J., & Williamson, D. P. (1995). Scheduling parallel machines on-line. SIAM Journal on Computing, 24, 1313–1331.
Wen, J., & Du, D. (1998). Preemptive on-line scheduling for two uniform processors. Operations Research Letters, 23, 113–116.
Woeginger, G. J. (2000). A comment on scheduling on uniform machines under chain-type precedence constraints. Operations Research Letters, 26, 107–109.