Worst-case analysis of LPT scheduling on a small number of non-identical processors

The approximation ratio of the longest processing time (LPT) scheduling algorithm has been investigated in various studies. While the tight approximation ratio is known for the cases when all processors are identical, the ratio is unknown when the processors have different speeds. In this study, we provide a tight approximation ratio for three, four, and five processors. We show that the ratios for these cases are no larger than the lower bound provided by Gonzalez et al. (1977) [14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively.

Automated summary

The investigation on the approximation ratio of the longest processing time (LPT) scheduling algorithm has been conducted in various studies. While the ratio is known for identical processors, it remains unknown for processors with different speeds. This study provides a tight approximation ratio for three, four, and five processors, showing that the ratios are no larger than the lower bound provided by Gonzalez et al. (1977) [14]. The ratios are approximately 1.38, 1.43, and 1.46 for three, four, and five processors, respectively.