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.
ASJC Scopus subject areas
- Applied Mathematics