| 带缓冲区的平行机半在线排序问题的近似算法 |
| |
| 引用本文： | 闵啸,耕田.带缓冲区的平行机半在线排序问题的近似算法[J].嘉兴学院学报,2005,17(3):31-35. |
| |
| 作者姓名： | 闵啸 耕田 |
| |
| 作者单位： | 嘉兴学院数学与信息科学学院,浙江,嘉兴,314001 |
| |
| 基金项目： | 嘉兴学院校重点课题论文,(课题编号:70103006) |
| |
| 摘 要： | 该文首先指出Kellerer(1997)关于带缓冲区的两台平行机半在线排序问题竞争比为4／3最优算法证明中一个不够严密的环节，并给予修正。然后将情况推广到三台平行机，给出了竞争比为3／2的近似算法，并给出了一个15／11的下界。
|
| 关 键 词： | 半在线 排序 近似算法 竞争比 |
| 文章编号： | 1008-6781(2005)03-0031-05 |
| 修稿时间： | 2004年7月20日 |
Approximation Algorithm for Parallel Machine Scheduling with a Buffer |
| |
| MIN Xiao,Geng Tian.Approximation Algorithm for Parallel Machine Scheduling with a Buffer[J].Journal of Jiaxing College,2005,17(3):31-35. |
| |
| Authors: | MIN Xiao Geng Tian |
| |
| Abstract: | In this paper we first point out a flaw in the proof of the 4/3 competitive ratio of the approximation algorithm for two parallel machine scheduling with a buffer and give a revision. Then we extend to consider the three parallel machines scheduling problem with a buffer and a approximation algorithm with 3/2 competitive ratio is proposed .At last,we provide a lower bound of this version as 15/11. |
| |
| Keywords: | semi on-line scheduling approximation algorithm competitive ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
