An LPT-Bound for a Parallel Multiprocessor Scheduling Problem

Farid Harche, Sridhar Seshadri

Research output: Contribution to journalArticlepeer-review


This paper is concerned with the problem of assigning n jobs with known processing times to m machines to minimize makespan. Each machine has a fixed capacity expressed as the maximum number of jobs that can be assigned to it. We investigate the worst-case behavior of the longest processing time heuristic for this problem. For the case of two machines with equal capacity, it is shown that the worst case error bound is 7/6.

Original languageEnglish (US)
Pages (from-to)181-195
Number of pages15
JournalJournal of Mathematical Analysis and Applications
Issue number1
StatePublished - Nov 15 1995
Externally publishedYes

ASJC Scopus subject areas

  • Analysis
  • Applied Mathematics


Dive into the research topics of 'An LPT-Bound for a Parallel Multiprocessor Scheduling Problem'. Together they form a unique fingerprint.

Cite this