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 language||English (US)|
|Number of pages||15|
|Journal||Journal of Mathematical Analysis and Applications|
|State||Published - Nov 15 1995|
ASJC Scopus subject areas
- Applied Mathematics