کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427747 | 686551 | 2012 | 4 صفحه PDF | دانلود رایگان |
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.
Journal: Information Processing Letters - Volume 112, Issue 10, 31 May 2012, Pages 376–379