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

摘要

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