l_2范数下两台带缓冲区同型机半在线排序问题的最优算法  

Semi on-line scheduling problem on two identical machines with a buffer under the l_2 norm

作　　者：闵啸[1] 刘静[1] 

机构地区：[1]嘉兴学院数学与信息科学学院,浙江嘉兴314001

出　　处：《浙江大学学报（理学版）》2008年第5期511-516,共6页Journal of Zhejiang University（Science Edition）

基　　金：嘉兴学院校重点科研课题资助(70106005)

摘　　要：研究一个带缓冲区(buffer)的两台同型平行机半在线排序模型.设有两台同型平行机,带有一个缓冲区,工件逐个到达,每当一个工件到达时可以被立即分配到机器上进行加工,也可以暂时存储在缓冲区中,加工不允许中断.目标为使两台机器最终负荷的l2范数最小.针对该模型只需缓冲区容量为1(在任一时刻至多存储1个工件),设计出一个最优半在线算法H,其竞争比为ρ≈1.076.A semi on-line scheduling problem on two identical machines under ι2 norm is investigated. In this semi on-line version a buffer of length 1 is available. When a job is arriving, one can either assign it to some machine or stock it in the buffer temporarily. Preemption is not allowed. The objective is to minimize the ι2 norm of the workloads on two machines. An optimal algorithm with a competitive ratio ρ≈1.076 is presented.

关 键 词：半在线 排序 缓冲区 ι2范数 竞争比 

分 类 号：O223[理学—运筹学与控制论]