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

A Model and Algorithm Analysis for Stochastic Online Scheduling on Uniform Machines

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

In this paper,we consider the stochastic online problem on m uniform parallel machines with the objective to minimize the total weighted expected completion times.In order to solve this problem,we first present a lower bound of the optimal value for the problem with the tool of linear programming relaxation,and then analyze the performance guarantee of the algorithm.