Parametric bounds for LPT scheduling on uniform processors (Q1179414)

The following deterministic scheduling problem is discussed. Independent tasks \(\{T_ 1,T_ 2,\dots,T_ n\}\) are processed by a multiprocessor system, which consists of \(m\) processors \(P_ 1,P_ 2,\dots,P_ m\). Every task may be processed by any processor (without preemptions). Every processor \(P_ j\) has its own speed \(s_ j\). Each task \(T_ i\) has a processing time \(t_ i\) when \(T_ i\) is processed by a processor with speed 1. The aim is to find an assignment (schedule) of tasks to the processors which minimize the makespan (the total completion time of all tasks). The problem is known to be \(NP\)-hard. New performance guarantees for LPT (largest processing time) algorithms are proposed. The LPT schedule is obtained as follows. All tasks are ordered in nonincreasing order of processing times, and the next task from the obtained list is assigned to that processor which will complete it earlier than any other processor. Let us denote a makespan for LPT and optimal schedule by \(f^ 0\) and \(f^*\) respectively, and \(r_ m=s_{\max}/s_{\min}\) where \(s_{\max}=\max_{1\leq j\leq m}s_ j\), \(s_{\min}=\min_{1\leq j\leq m}s_ j\). Then \[ 1+{{(3^{m+1}/\sqrt{e}2^ m)-3} \over {(3^{m+1}/\sqrt{e}2^ m)-2}} r_ m/3\leq f^ 0/f^*\leq 1+r_ m/3. \]