On-line scheduling of equal-length intervals on parallel machines

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.