Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs

We consider a scheduling problem with m identical machines in parallel and the minimum makespan objective. The Longest Processing Time first (LPT) rule is a well-known approximation algorithm for this problem. Although its worst-case approximation ratio has been determined theoretically, it is known that the worst-case approximation ratio of LPT can be smaller with instances of smaller processing times. We assume that each job’s processing time is not longer than 1/k times the optimal makespan for a given integer k. We derive the worst-case approximation ratio of the LPT algorithm in terms of parameters k and m. For that purpose, we divide the whole set of instances of the original problem into classes defined by different values of parameters k and m. On each of those classes, we derive an exact upper bound on the worst-case performance ratio as a function of parameters k and m. We also show that there exist classes of instances for which our worst-case approximation ratio is better than previous bounds. Our bound can complement previous research in terms of the performance analysis of LPT.