New Approximation Bounds for LPT Scheduling

We provide new bounds for the worst case approximation ratio of the classic Longest Processing Time (LPT) heuristic for related machine scheduling (Q parallel to C(max)). For different machine speeds, LPT was first considered by Gonzalez et al. (SIAM J. Comput. 6(1): 155-166, 1977). The best previously known bounds originate from more than 20 years back: Dobson (SIAM J. Comput. 13(4): 705-716, 1984), and independently Friesen (SIAM J. Comput. 16(3): 554-560, 1987) showed that the worst case ratio of LPT is in the interval (1.512, 1.583), and in (1.52, 1.67), respectively. We tighten the upper bound to 1+ root 3/3 approximate to 1.5773, and the lower bound to 1.54. Although this improvement might seem minor, we consider the structure of potential lower bound instances more systematically than former works. We present a scheme for a job-exchanging process, which, repeated any number of times, gradually increases the lower bound. For the new upper bound, this systematic method together with a new idea of introducing fractional jobs, facilitated a proof that is surprisingly simple, relative to the result. We present the upper-bound proof in parameterized terms, which leaves room for further improvements.