| 同类机随机在线排序模型及算法分析 |
| |
| 引用本文： | 顾满占,鲁习文.同类机随机在线排序模型及算法分析[J].医学教育探索,2009(6):942-946. |
| |
| 作者姓名： | 顾满占 鲁习文 |
| |
| 作者单位： | 华东理工大学理学院数学系;华东理工大学理学院数学系 |
| |
| 基金项目： | 国家自然科学基金(10771067) |
| |
| 摘 要： | 考虑同类机随机在线排序问题。假设有m台同类机，工件在线到达，问题的目标是使总加权完工时间的期望值最小。考察该随机在线问题，首先利用线性规划松弛的方法，得到问题最优解的一个下界； 然后给出解决该问题的一个在线算法，并分析了该算法的竞争比。
|
| 关 键 词： | 在线排序 随机排序 同类机 竞争比 |
| 收稿时间： | 2008/12/5 0:00:00 |
A Model and Algorithm Analysis for Stochastic Online Scheduling on Uniform Machines |
| |
| Abstract: | 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. |
| |
| Keywords: | online scheduling stochastic scheduling uniform machine performance guarantee |
|
| 点击此处可从《医学教育探索》浏览原始摘要信息 |
| 点击此处可从《医学教育探索》下载免费的PDF全文 |
