3台平行机上带有2个服务等级的离线负载均衡

摘要

排序问题是一类重要的组合最优化问题,在生产计划、计算机控制等领域有着广泛应用,一直是理论界研究热点。对带服务等级的3台平行机排序问题进行研究,每台机器和每个工件都有等级标号,每个工件只能被某台服务等级不高于该工件等级的机器加工,目标是最小化最大机器的完工时间。运用新的算法思想解决离线状态等级约束下的3台机器负载均衡问题。对等级约束为1、2、2的3台平行机给出一个43-近似算法;对于等级约束为1、1、2的3台平行机给出一个2-近似算法。