|
|||||
|
|
| 带机器准备时间的平行机ordinal排序及近似算法 | |
| 引用本文： | 谈之奕,何勇. 带机器准备时间的平行机ordinal排序及近似算法[J]. 应用数学学报, 2002, 25(2): 223-229 |
| 作者姓名： | 谈之奕 何勇 |
| 作者单位： | 浙江大学数学系,杭州,310027 |
| 基金项目： | 国家973重点基础研究专项经费（G1998030401（2）），高等学校优秀青年教师教学科研奖励计划资助项目. |
| 摘 要： | 本文研究带机器准备时间的m台平行机ordinal在线排序问题。讨论了在极小化最大机器完工时间和极小化最大工件完工时间两种目标下的不同下界和相应的在线近似算法。对第一个目标，我们得到了3/2的下界和最坏情况界为2-1/m的近似算法。对第二个目标，我们得到了最坏情况为m的最好近似算法。我们还对一些特殊情况进行了分析。 |
| 关 键 词： | 机器准备时间 平行机 ordinal排序 近似算法 半在线排序 最坏情况界 排序问题 |
Ordinal On-line Scheduling on Parallel Machines with Machine Release Times |
|
| TAN ZHIYI HE YONG. Ordinal On-line Scheduling on Parallel Machines with Machine Release Times[J]. Acta Mathematicae Applicatae Sinica, 2002, 25(2): 223-229 | |
| Authors: | TAN ZHIYI HE YONG |
| Abstract: | Abstract This paper investigates ordinal on-line scheduling on parallel machines with machine release times. Two objects of minimizing the last machine completion time and minimizing the last job completion time are considered. For the first object, we present an algorithm with worst-case ratio of 2 ?1/m. For the second object, we show that the best possible algorithm has a worst-case ratio of m. We further consider three special cases. |
| Keywords: | Semi on-line scheduling approximation algorithm worst-case ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |