文献类型：期刊文献

中文题名：同类机随机在线排序模型及算法分析

英文题名：A Model and Algorithm Analysis for Stochastic Online Scheduling on Uniform Machines

作者：顾满占[1];鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2009

卷号：35

期号：6

起止页码：942

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;Scopus;北大核心:【北大核心2008】；CSCD:【CSCD2011_2012】；

基金：国家自然科学基金(10771067)

语种：中文

中文关键词：在线排序;随机排序;同类机;竞争比

外文关键词：online scheduling stochastic scheduling uniform machine performance guarantee

摘要：考虑同类机随机在线排序问题。假设有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.