\input zb-basic
\input zb-ioport
\iteman{io-port 06103788}
\itemau{Cheng, T.C.E.; Kellerer, Hans; Kotov, Vladimir}
\itemti{Algorithms better than LPT for semi-online scheduling with decreasing processing times.}
\itemso{Oper. Res. Lett. 40, No. 5, 349-352 (2012).}
\itemab
Summary: We consider the semi-online multiprocessor scheduling problem with $m$ 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 {\it R. L. Graham} [SIAM J. Appl. Math. 17, 416--429 (1969; Zbl 0188.23101)] 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)$. 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/4$-competitive algorithm for $m \ge 3$ and an algorithm that is the best possible for $m=3$, i.e., an algorithm with competitive ratio $(1+\sqrt{37})/6$.
\itemrv{~}
\itemcc{}
\itemut{online algorithms; semi-online algorithms; competitive ratio; multiprocessor scheduling}
\itemli{doi:10.1016/j.orl.2012.05.009}
\end