针对经典排序问题的一种新算法的近似比分析

Approximate Ratios Analysis of New Algorithm for Classical Parallel Scheduling

给定m台平行机(同型机),n个工件,寻找一种分配方案,使得把这n个工件分配到m台机器后,整体完工时间尽可能短,这个NP-难问题被称为经典排序问题。如果每个工件的加工时间满足一定的条件,则有望能在多项式时间内有效地得到最优的分配方案。Yue等对加工时间满足整除性质的经典排序问题考虑了一种新的算法,该算法总是能得到这种特殊情况的最优分配。该算法在多项式时间内能够得到最优分配,是对于一般的经典排序问题的近似算法。文章在此基础上,考虑该新算法在一般问题上的近似比。文中考虑了这个新算法的两种版本,分别得到了3/2和2-1/2 ^(q)(q∈Z^(+))的近似比。紧例子表明,文中对算法的两个版本的分析都是最优的。

Given m parallel machines(identical machines)and n jobs,we need to find a distribution scheme so that the overall completion time is as short as possible after these n jobs are allocated to m machines.This NP-hard problem is called classical scheduling problem.If the processing time of each job meets certain conditions,it is expected to get the optimal allocation scheme effectively.Yue et al.consider a new algorithm for the classical scheduling problem that the processing time satisfies the divisional property,which can always obtain the optimal distribution in this special case.This algorithm can obtain the optimal distribution in polynomial time and is an approximate algorithm for the general classical scheduling problem.On this basis,the approximate ratio of the algorithm in general problems is considered.There are two versions of the proposed algorithm,and the approximate ratios of 3/2 and 2-1/2 ^(q)(q∈Z^(+))are obtained respectively.The tight examples provided in this paper show that our analysis of two versions of the algorithm is optimal.