|
|||||
|
|
| 一个可中断两台可拒绝同型机半在线排序问题 | |
| 引用本文： | 闵啸,张玉才. 一个可中断两台可拒绝同型机半在线排序问题[J]. 浙江大学学报(理学版), 2007, 34(5): 509-514 |
| 作者姓名： | 闵啸 张玉才 |
| 作者单位： | 1. 嘉兴学院,数学与信息科学学院,浙江,嘉兴,314001 2. 嘉兴学院,人文社科训练中心,浙江,嘉兴,314001 |
| 摘 要： | 讨论一个两台可拒绝同型机半在线排序问题的近似算法．设有两台同型机，工件逐个到达，可以被接收加工，消耗一定的加工时间tj，也可以被拒绝，但要付出一定的罚值Pj，目标是使被加工工件集的最大完工时间（makespan）和被拒绝工件集的罚值之和最小．此外，进一步假定每个工件的罚值和加工长度事先形成固定的比例α∈[0，＋∞），即Pi=atj，针对工件加工可中断情形，设计出近似算法PRH，证明其竞争比．同时又给出该问题的下界，它们均为α的分段函数，且算法PRH在a∈[0，√2/2）∪[5/6＋∞）达到最优． |
| 关 键 词： | 半在线 排序 可拒绝 可中断 同型机 近似算法 竞争比 |
| 文章编号： | 1008-9497（2007）05-509-06 |
| 修稿时间： | 2006-03-09 |
Preemptive semi-on-line scheduling on two identical machines with rejection |
|
| MIN Xiao,ZHANG Yu-cai. Preemptive semi-on-line scheduling on two identical machines with rejection[J]. Journal of Zhejiang University(Sciences Edition), 2007, 34(5): 509-514 | |
| Authors: | MIN Xiao ZHANG Yu-cai |
| Affiliation: | 1. Department of Mathematics and Information, Jiaxing College, Jiaxing 314001, China ; 2. Humanity and Social Sciences Training Center, Jiaxing College, Jiaxing 314001, China |
| Abstract: | |
| Keywords: | semi-on-line scheduling rejection preemptive identical machines approximation algorithm competitive ratio |
| 本文献已被 维普 万方数据 等数据库收录！ | |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 | |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 | |