关键词:
云计算
多阶段工作
多处理机调度
近似算法
算法分析
摘要:
随着大数据对人们生活的影响逐渐增大,数据存储和计算需求不断增加,云计算的兴起有效地满足了这一需求。在实时性要求较高的云计算系统中,来自客户端的资源请求被视为具有截止期限和一定收益的两阶段工作,云服务器被视为两阶段机器。不同资源请求的截止期限通常不同,如果云中心能在资源请求的截止期限之前完成该请求,就可以获得相应的收益。现有的以收益最大化作为优化目标的两阶段工作调度均是在一个公共截止期限制下进行的,而实际情况往往是不同的资源请求可能有不同的截止期限。基于当前云计算应用和数据中心数据处理的需求,建立了云计算系统中工作调度的新数学模型。首次提出了具有多个截止期的两阶段工作在多处理机上的调度问题,并给出了一个近似比为(3 k+ε)的多项式时间近似算法。当机器数目为固定常数时,近似比进一步降低为(k+ε),其中k是一个固定常数,即截止期的个数,ε是大于0的任意常数。针对特殊的T-处理时间大于R-处理时间模型,在单个两阶段机器上,给出了一个近似比为2的伪多项式时间近似算法,进一步降低了算法的近似比。