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 T1≤ M M-1Ti-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 ∀1, E[V1]+≤ m(m-1) 2(n+1), where E[Vi]+ is an upper bound of the expected system idle time with respect to job i.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research