Performance of the LPT algorithm in multiprocessor scheduling

The performance of the longest processing time first algorithm (LPT) in multiprocessor scheduling is investigated. The worst-case analysis for the deterministic models is performed when the processing times (Ti’s) are nondecreasingly ordered (T1•T2•ëëë•Tn). If Ti•(m/(m-1))TiÅ-1, ℝi 2•i•n, then RL, the ratios of the makespans of the LPT schedules to the optimal schedules, is less than or equal to 1+(m-1)/n. In addition, a stochastic model is studied which shows that if Ti’s are order statistics of n draws from the uniform distributed interval [0,1], then ℝi, E[Vi]Å+•m(m-1)/2(n+1), where E[Vi]Å+ is an upper bound of the expected system idle time with respect to job i.