| 带机器准备时间的平行机在线与半在线排序 |
| |
| 引用本文： | 谈之奕,何勇.带机器准备时间的平行机在线与半在线排序[J].系统科学与数学,2002,22(4):414-421. |
| |
| 作者姓名： | 谈之奕 何勇 |
| |
| 作者单位： | 浙江大学数学系,杭州,310027 |
| |
| 基金项目： | 国家自然科学基金，高等学校优秀青年教师教学科研奖励计划资助课题 |
| |
| 摘 要： | 本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。
|
| 关 键 词： | 在线排序 近似算法 最坏情况分析 |
| 修稿时间： | 2000年3月21日 |
ON-LINE AND SEMI ON-LINE SCHEDULING ON PARALLEL MACHINES WITH NON-SIMULTANEOUS MACHINE AVAILABLE TIMES |
| |
| Zhi Yi TAN,Yong HE.ON-LINE AND SEMI ON-LINE SCHEDULING ON PARALLEL MACHINES WITH NON-SIMULTANEOUS MACHINE AVAILABLE TIMES[J].Journal of Systems Science and Mathematical Sciences,2002,22(4):414-421. |
| |
| Authors: | Zhi Yi TAN Yong HE |
| |
| Institution: | Department of Mathematics, Zhejiang University, Hangzhou 310027,P.R.China |
| |
| Abstract: | This paper investigates on-line and semi on-line scheduling problems on parallel machines with non-simultaneous machine available times. In on-line version, we prove that the worst-case ratio of LS algorithm is 2 -1/m. Three semi on-line scheduling problems are studied, where the jobs are ordered in decreasing processing times, the total processing time or the largest processing time being known in advance. For each problem, we analyze its lower bound and give its approximation algorithms. The algorithms are all the best possible ones for a two-machine case. |
| |
| Keywords: | On-line scheduling approximation algorithms worst-case analysis |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
| 点击此处可从《系统科学与数学》下载免费的PDF全文 |
|
