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

Semi-online Scheduling with Machine Cost

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

For most scheduling problems the set of machines is fixed initially and remains unchanged for the duration of the problem.In the authors first proposed adding the concept of machine cost to scheduing problems and considered the so called list model problem.An online algorithm with a competitive ratio less than(1+5)/2≈1.618 was given while the lower bound is 4/3.In this paper,we assume that the processing time of the largest job is known as a priori.We present a semi online algorithm with competitive ratio at most 19/12≈1.583 while the lower bound is 4/3.It verifies that additional partial available information about the jobs admit the possibility of constracting a schedule with a smaller competitive ratio than that of online algorithms.