An alternative proof of the Kawaguchi–Kyan bound for the Largest-Ratio-First rule

In a well-known paper from 1986, Kawaguchi and Kyan proved that the Largest-Ratio-First rule for total weighted completion time scheduling on identical parallel machines has a worst case ratio of 12(1+2). We provide an alternative and simple proof for this result.

► Kawaguchi and Kyan proved a worst case ratio for Largest-Ratio-First scheduling. ► The original proof is rather long and involved. ► We provide an alternative proof by showing sets of simple worst case instances.