预先知道工件最大加工时间的带机器费用的排序

对大多数排序问题来说 ,机器集往往是事先给定的 ,而且在算法进行过程中 ,机器集是不变的 . Imreh和Noga[2 ] 第一次提出了在排序中考虑机器费用的模型 .他们研究了所谓的ListModelproblem ,并给出了 竞争比为 (1+5 ) / 2≈ 1.6 18的在线算法 ,同时证明了该模型的任意在线算法的竞争比至少是 4 / 3.本文研究 ListModelproblem的一个半 在线情形 ,我们假设工件的最大加工时间预先知道 ,我们将给出一个竞争比为 19/ 12≈ 1.5 83的半在线算法 ,同时证明对该问题的这一半在线情形 ,任意半在线算法的竞争比至少是 4 / 3.