Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
427747 | Information Processing Letters | 2012 | 4 Pages |
We consider the on-line preemptive scheduling of weighted equal-length intervals on multiple machines to maximize the total weight of completed intervals. We design an algorithm that is 2-competitive when the number of machines m is even; and (2+22m−1)-competitive when m is an odd number at least 3. For example, when m=3m=3, it is 2.4-competitive. As m increases, the competitive ratio approaches 2.
► We design an on-line algorithm for scheduling weighted equal-length intervals on identical machines. ► When the number of machines is even, our algorithm is 2-competitive, improving and generalizing the best previous result. ► When the number of machines is odd, our algorithm has a novel mechanism to distribute the intervals among the machines.