摘要
We address the problem of preemptively schedule on-line jobs on arbitrary m uniformly related machines with the objective of minimizing the schedule length. We provide the first on-line algorithm for this general problem, and show that the algorithm has a competitive ratio of 1 ± σ, where a (m - 1)s1/(si +…+ sm), S1 S2 Sm being the speeds of the m machines.
We address the problem of preemptively schedule on-line jobs on arbitrary m uniformly related machines with the objective of minimizing the schedule length. We provide the first on-line algorithm for this general problem, and show that the algorithm has a competitive ratio of 1 ± σ, where a (m - 1)s1/(si +…+ sm), S1 S2 Sm being the speeds of the m machines.
基金
This research is supported by National Natural Science Foundation of China
Shandong Province the Foundation for University
