|
|||||
|
|
| 三台平行机排序的一个复合半在线问题的算法 | |
| 引用本文： | 华荣伟,胡觉亮,卢璐.三台平行机排序的一个复合半在线问题的算法[J].管理工程学报,2006,20(3):100-103. |
| 作者姓名： | 华荣伟 胡觉亮 卢璐 |
| 作者单位： | 1. 浙江大学数学系,浙江,杭州,310027;浙江医学高等专科学校,浙江,杭州,310053 2. 浙江理工大学,浙江,杭州,310033 3. 英特尔产品上海有限公司,上海,200031 |
| 摘 要： | 本文讨论一个三台平行机半在线排序问题.对预先知道工件的总加工时间和最大的工件的加工时间的复合半在线模型,我们证明了不存在半在线算法,其竞争比为4/3,并给出了一个竞争比为7/5的半在线算法,两者的差距小于0.067. |
| 关 键 词： | 排序 半在线 近似算法 |
| 文章编号： | 1004-6062(2006)03-0100-04 |
| 修稿时间： | 2004年3月22日 |
A Semi-Online Algorithm for Parallel Machine Scheduling on Three Machines |
|
| HUA Rong-wei,HU Jue-liang,LU Lu.A Semi-Online Algorithm for Parallel Machine Scheduling on Three Machines[J].Journal of Industrial Engineering and Engineering Management,2006,20(3):100-103. | |
| Authors: | HUA Rong-wei HU Jue-liang LU Lu |
| Abstract: | This paper considers a semi-online parallel machine scheduling problem on a 3-machine system.We assume that the total processing time of all jobs and the largest processing time are known in advance.We present a new semi-online algorithm with competitive ratio 7/5 while no algorithm can have competitive ratio smaller than 4/3.The gap between them is less than 0.067. |
| Keywords: | scheduling semi-online approximation algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |