Generalization of EDF and LLF: Identifying All Optimal Online Algorithms for Minimizing Maximum Lateness
Tóm tắt
It is well known that the Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF) algorithms are optimal algorithms for the problem of preemptively scheduling jobs that arrive over time on a single machine to minimize the maximum lateness (1|r
j
,pmtn|L
max ). It was not previously known what other online algorithms are optimal for this problem. As this problem is fundamental in machine scheduling, it deserves a thorough investigation. In this paper, the concept of compound laxity is introduced, and a complete characterization of all optimal online algorithms for this problem is derived.
Tài liệu tham khảo
Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974), Chap. 2
Chan, H.-L., Lam, T.-W., To, K.-K.: Nonmigratory online deadline scheduling on multiprocessors. SIAM J. Comput. 34(3), 669–682 (2005)
Dertouzos, M., Mok, A.: Multiprocessor on-line scheduling of hard-real-time tasks. IEEE Trans. Softw. Eng. 15, 1497–1506 (1989)
Dertouzos, M.L.: Control robotics: the procedural control of physical processes. In: Proceeding of IFIP Congress, pp. 807–813 (1974)
Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)
Koo, C.-Y., Lam, T.-W., Ngan, T.-W., To, K.-K.: Extra processors versus future information in optimal deadline scheduling. In: Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 133–142 (2002)
Lam, T.W., To, K.-K.: Performance guarantee for online deadline scheduling in the presence of overload. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 755–764 (2001)
Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 140–149 (1997)
Rasala, A., Stein, C., Torng, E., Uthaisombut, P.: Existence theorems, lower bounds and algorithms for scheduling to meet two objectives. In: Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 723–731 (2002)