局内同类机器加工任务排序问题的一种算法及仿真试验

An Algorithm And Its Emulational Experiment of On-line Scheduling Tasks on Uniform Machines Problem

对于局内同类机器加工任务排序问题设计了一种SpacePreparation算法 (简称SP算法 ) ,改进了经典LIST算法的平均执行效率 .文中证明SP算法的竞争比为 2 。

For on\|line scheduling tasks on uniform machines problem, a new method named space preparation(Abbr. SP) algorithm is designed to improve classical LIST algorithm's average performance efficiency. The competitive ratio of SP algorithm is proved to be 2 and its average performance efficiency is verified with its emulational experiment.