کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1142389 | 957145 | 2012 | 4 صفحه PDF | دانلود رایگان |
We consider the semi-online multiprocessor scheduling problem with mm identical, parallel machines to minimize the makespan, where the jobs arrive in decreasing order of processing times. The famous Longest Processing Time (LPT) algorithm by Graham (1966) [4] for the classical offline multiprocessor scheduling problem schedules the jobs in decreasing order of processing times and has a worst-case bound of 4/3−1/(3m)4/3−1/(3m). So far, no algorithm with a better competitive ratio than the LPT algorithm has been given for the semi-online scheduling problem with decreasing processing times. In this note, we present a 5/45/4-competitive algorithm for m≥3m≥3 and an algorithm that is the best possible for m=3m=3, i.e. an algorithm with competitive ratio (1+37)/6.
Journal: Operations Research Letters - Volume 40, Issue 5, September 2012, Pages 349–352