| P‖Cmin随机算法研究 |
| |
| 引用本文： | 谈之奕,何勇. P‖Cmin随机算法研究[J]. 应用数学学报, 2002, 25(4): 746-751 |
| |
| 作者姓名： | 谈之奕 何勇 |
| |
| 作者单位： | 浙江大学数学系,杭州,310027 |
| |
| 基金项目： | 国家973重点基础研究专项经费(G1998030401(2))，高等学校优秀青年教师教学科研奖励计划资助项目 |
| |
| 摘 要： | 本文研究了P‖Cmin的随机算法及其最坏情况界，我们给出了Pm‖Cmin在线排序问题新的随机上界，并给出了P2‖Cmin的最好随机算法，其最坏情况界为2／3。对P2‖Cmin已知工件加工时间递减半在线模型，我们给出了一最坏情况界为6／7的随机算法并证明了它为最好的。
|
| 关 键 词： | 在线排序 随机算法 最坏情况界 |
RANDOMIZED ALGORITHMS ON PARALLEL MACHINE SCHEDULING |
| |
| TAN ZHIYI HE YONG. RANDOMIZED ALGORITHMS ON PARALLEL MACHINE SCHEDULING[J]. Acta Mathematicae Applicatae Sinica, 2002, 25(4): 746-751 |
| |
| Authors: | TAN ZHIYI HE YONG |
| |
| Abstract: | In this paper, we present randomized algorithms for parallel machine scheduling with objective to maximize the minimum machine completion time. We give a new lower bound for general m > 1 machines case. For m = 2, we present best possible randomized algorithms for its on-line version and a semi on-line version with job decreasing processing time. |
| |
| Keywords: | On-line scheduling randomized algorithm worst-case ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
