主权项 |
一种用于改善最差等待时间的工作划分方法,适用于将N笔资料项分配到C个频道以进行广播,其中,该等资料项所形成的一资料集合表示为D={d1,d2,...,dN},该方法系以电脑来实现并包含下列步骤:(A)接收来自于至少一客户端的m个查询集合,其中,Qi代表第i个查询集合,对于i=1,2,...,m,QiD,,该等查询集合形成一查询资料集合组并表示为AP(m)={Q1,Q2,...,Qm};(B)根据该查询资料集合组的该等查询集合来初始化一工作划分结果,其中,该工作划分结果包括分别对应于该等频道的C个工作,该工作划分结果表示为π={P1,P2,...,PC},Pi代表第i个工作,Pi包括其分配到的查询集合的资料项,,|Pi|代表第i个工作所包括的资料项数目,经过初始化的该工作划分结果满足以下的一工作大小排序:;(C)以PC-β+1,PC-β+2,...,PC作为β个候选工作,其中,β为预设的一候选者临界值;(D)判断是否存在满足预设的一调整条件的查询集合及工作,其中,该调整条件为:自P1将此查询集合移到该等候选工作其中之一Pj,j{C-β+1,C-β+2,...,C},可使得|P1|所减少的数量为目前最多,且同时使得|Pj|所增加的数量为目前最少;(E)若步骤(D)的判断结果为是,则执行以下子步骤:(e-1)将符合该调整条件的查询集合自P1移到符合该调整条件的Pj;(e-2)调整该工作划分结果使其调整后满足该工作大小排序:;及(e-3)回到步骤(D)之判断;(F)若步骤(D)的判断结果为否,则依一微调规则进行微调;以及(G)若步骤(F)的微调结果为不成功,即,无法依该微调规则进行微调,则以此时的该工作划分结果作为一近似最佳工作划分结果,其中,该近似最佳工作划分结果系用以作为将该等资料项分配到该等频道以进行广播的依据。 |