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

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

研究一个带缓冲区(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.