同类机随机在线排序模型及算法分析

考虑同类机随机在线排序问题。假设有m台同类机，工件在线到达，问题的目标是使总加权完工时间的期望值最小。考察该随机在线问题，首先利用线性规划松弛的方法，得到问题最优解的一个下界；然后给出解决该问题的一个在线算法，并分析了该算法的竞争比。