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

研究一个带缓冲区（buffer）的两台同型平行机半在线排序模型。设有两台同型平行机，带有一个缓冲区，工件逐个到达，每当一个工件到达时可以被立即分配到机器上进行加工，也可以暂时存储在缓冲区中，加工不允许中断。目标为使两台机器最终负荷的l2范数最小。针对该模型只需缓冲区容量为1（在任一时刻至多存储1个工件，设计出一个最优半在线算法H，其竞争比为p≈1.076。