Algorithms better than LPT for semi-online scheduling with decreasing processing times

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.