Performance of the LPT algorithm in multiprocessor scheduling

Tien Y. Kao, E. A. Elsayed

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)365-373
Number of pages9
JournalComputers and Operations Research
Volume17
Issue number4
DOIs
StatePublished - 1990

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Performance of the LPT algorithm in multiprocessor scheduling'. Together they form a unique fingerprint.

Cite this