## 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 (T_{i}'s) are nondecreasingly ordered (T_{1} ≤ T_{2} ≤ ... ≤ T_{n}). If T_{1}≤ M M-1T_{i-1},∀i, 2≤i≤n, then R_{L}, 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 T_{i}'s are order statistics of n draws from the uniform distributed interval [0, 1], then ∀1, E[V_{1}]+≤ m(m-1) 2(n+1), where E[V_{i}]_{+} is an upper bound of the expected system idle time with respect to job i.

Original language | English (US) |
---|---|

Pages (from-to) | 365-373 |

Number of pages | 9 |

Journal | Computers and Operations Research |

Volume | 17 |

Issue number | 4 |

DOIs | |

State | Published - 1990 |

## All Science Journal Classification (ASJC) codes

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