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

作者：Schwiegelshohn Uwe^*

来源：Operations Research Letters, 2011, 39(4): 255-259.

DOI：10.1016/j.orl.2011.06.007

• Total weighted completion time scheduling
• Worst case analysis
• Performance guarantee

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 1/2(1 + root 2). We provide an alternative and simple proof for this result.

• 出版日期2011-7