机器不同时开工排序问题算法A_(KK)的最坏情况性能比

The Worst-Case Ratio of Algorithm A_(KK) for Parallel Machines Scheduling with Non-simultaneous Machine Available Times

对于经典排序中的同型机(identical machines)排序问题Pm||Cmax,1969年Graham根据Kleitman和Knuth的建议提出著名的近似算法——算法AKK。2005年李红英等对于算法AKK提出改进的最坏情况性能比。机器不同时开工排序问题Pm,ai||Cmax是经典的同型机排序问题的推广,是一种新型排序。把算法AKK用到机器不同时开工排序问题Pm,ai||Cmax上去,得到新的最坏情况性能比,并把此最坏情况性能比与Graham得到的和李红英等人得到的最坏情况性能比进行了比较。

The identical parallel machine scheduling problem Pm‖Cmax is a classical scheduling problem. Following a suggestion of D.Kleitman and D.Knuth, Graham proposed a famous approximation algorithm Algorithm AKK in 1969. And in 2005, an improved worst-case ratio for it was gotten by Li Hongying et al. In this paper, identical parallel machines scheduling problem with non-simultaneous machine available time was considered. It is a new type of scheduling. The algorithm AKK was applied to this problem Pm,ai‖Cmax, and the new worst-case ratio has been obtained. Finally, the comparisons of our results to Graham＇s and Li Hongying＇s were carried on.