平行机在线(半在线)排序问题近似算法研究

A Research on the Approximation Algorithm of On-line Scheduling on Identical Machine

主要研究三台平行机三种不同类型的半在线排序问题。通过最优情况分析或数值方法评价其性能。得到第一种第二种情况的最坏性能都不超过预期的5／3,第三种情况依罚值与工件长度的固定比值的不同而有不同的算法,当α小于3^(1/2)／3时将拒绝所有的工件,否则接受所有的工件并按照LS法将工件进行排序。进一步证明其竞争比为α的分段函数。

In this paper we investigate three different semi on-line versions of the partition problem on three identical machines. Investigate its performance ratio by worst case analysis or numerical method. In the first case, we present an approximation algorithm with competitive ratio which does not exceed 5/3. We also present an approximation algorithm with competitive ratio that is not larger than 3/2 for the second one. In the third case, we present an approximation algorithm which is decided byα.Whenαis smaller than 3^(/2)/3,we reject all the job, otherwise,we accept all the jobs, and schedule the jobs according to LS rule. Finally, we prove the competitive ratio which is decided byα.