| 同类机半在线排序问题及其近似算法 |
| |
| 引用本文： | 谈之奕,何勇.同类机半在线排序问题及其近似算法[J].系统工程理论与实践,2001,21(2):53-57. |
| |
| 作者姓名： | 谈之奕 何勇 |
| |
| 作者单位： | 浙江大学数学系 |
| |
| 基金项目： | 国家973重点基础研究专项经费;国家自然科学基金(19701028) |
| |
| 摘 要： | 研究两台同类机系统两个半在线排序问题 .第一个为总加工时间已知 ,第二个为最大工件加工时间已知 .对这两个问题 ,文章给出了各自的近似算法 ,证明了它们的最坏情况界分别为 3和3/2 .文章还研究了上述问题的下界并与我们的算法的最坏情况界进行了比较.
|
| 关 键 词： | 在线排序 近似算法 最坏情况分析 |
| 文章编号： | 1000-6788(2001)02-0053-05 |
| 修稿时间： | 1999年6月29日 |
Semi On-Line Scheduling on
Two Uniform Machines |
| |
| TAN Zhi-yi,HE Yong.Semi On-Line Scheduling on
Two Uniform Machines[J].Systems Engineering —Theory & Practice,2001,21(2):53-57. |
| |
| Authors: | TAN Zhi-yi HE Yong |
| |
| Institution: | Department of Mathematics, Zhejiang University |
| |
| Abstract: | This paper investigates two semi on\|line scheduling problems on a two uniform machine system. In the first case, we assume that the total processing time is known in advance. In the second case, we assume that the largest processing time is known in advance. For each case we propose a heuristic and investigate its worst\|case ratio. |
| |
| Keywords: | On\|line scheduling approximation algorithm worst\|case ratio |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
