吴用;杨启帆
平行机排序问题广泛出现并应用于各领域,如通讯网信道分配的负载均衡, 大型计算中的并行计算,
柔性制造系统的任务编排等等.研究了预知工件大小上界的半在线平行机排序问题.考察了仅预知工件大小上界和既预知工件大小上界又预知最优目标值的两类半在线模型.基于资源分配公平性和提高服务质量的考虑,针对每类模型都分别考察了两个目标:$C_{\rm max}$(极小化机器最大负载~makespan) 和~$C_{\rm min}$(极大化机器最小负载).在不同的目标下,针对~$m$ 台平行机的一般情况均给出了问题的下界并设计了半在线算法,某些情况下设计的算法是最优算法.