Worst-Case Analysis of LPT Scheduling on Small Number of Non-Identical Processors

Takuto Mitsunobu, Reiji Suda, Vorapong Suppakitpaisarn

The approximation ratio of the longest processing time (LPT) scheduling algorithm has been studied in several papers. While the tight approximation ratio is known for the case when…