|
|||||
|
|
| 已知工件最大加工时间的两台同类机半在线问题 | |
| 引用本文： | 罗润梓,孙世杰. 已知工件最大加工时间的两台同类机半在线问题[J]. 系统科学与数学, 2006, 26(6): 729-736 |
| 作者姓名： | 罗润梓 孙世杰 |
| 作者单位： | 1. 南昌大学数学系,南昌,330047 2. 上海大学数学系,上海,200444 |
| 摘 要： | 考虑已知工件最大加工时间的两台同类机半在线问题．机器M1,M2的速度分别为s1=1,s2=s(s≥1),工件是一个一个独立地到来,工件的信息是逐个释放的,但所有工件中加工时间为最大的工件的加工时间是已知的,目标函数为极小化最大机器负载．此模型简记为Q2／known largest job／Cmax．作者给出了Qmax2算法并证明此算法的竞争比为2(s 1)/s 2(1≤s≤2)和(s 1)/s(s>2),且是紧的．同时给出Q2／known largest job／Cmax问题的一个下界,并且证明Qmax2算法的竞争比与最优算法竞争比之差不大于1/4. |
| 关 键 词： | 半在线 同类机 竞争比 |
| 收稿时间： | 2003-11-26 |
| 修稿时间： | 2003-11-26 |
Semi on-line scheduing problem with the largest processing time of jobs on two uniform machines known |
|
| Luo Runzi,Sun Shijie. Semi on-line scheduing problem with the largest processing time of jobs on two uniform machines known[J]. Journal of Systems Science and Mathematical Sciences, 2006, 26(6): 729-736 | |
| Authors: | Luo Runzi Sun Shijie |
| Affiliation: | (1)Department of Mathematics, Nanchang University, Nanchang 330047;(2)Department of Mathematics, Shanghai University,Shanghai 200444 |
| Abstract: | |
| Keywords: | Semi on-line uniform machine competitive ratio. |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 | |
| 点击此处可从《系统科学与数学》下载全文 | |