摘要：探讨两台机器上工件具有权重和服务等级约束的平行批在线排序问题。根据工件和机器的特性,有相应的等级约束。工件只能在服务等级不高于自身等级的机器上加工。工件按时在线释放,具有权重和相同的加工时间。机器可以平行批处理工件,在不超过批容量的情形下,多个工件可以用一台机器在一批中同时进行加工。目标函数是最小化所有工件的最大加权完工时间。讨论该问题的时间在线排序算法,给出了在线算法竞争比的下界,并设计了与下界√5+1/2匹配的最好可能的在线算法。

摘要：现有服务承载网的构建方法均未考虑用户请求所属的业务类别,导致业务承载与服务供应缺少有效的串联.针对该问题,提出了一种新型的端到端服务供应模型,从承载同类别业务的角度构建服务承载网,通过在服务承载网上构建服务路径提供可定制的端到端服务.为验证模型的可行性和有效性,设计了一种基于跳数约束的服务承载网构建算法,并使用经典的Layered Graph算法构建服务路径.实验结果体现了在不同的负载压力下,跳数约束对开销、收益、接受率、路径长度等性能评价指标的影响,从而验证了模型和算法的有效性,提供了性价比最优的服务承载网构建决策.当跳数约束等于3时,取得了与跳数约束等于4或5时相近的性能,同时分别节省了约50%或75%的构建开销.