单机等长区间的在线排序问题研究

Research on the onlie scheduling of equal-length intervals on a single machine

在单机区间排序环境中定义了一种新的半在线排序模型:区间是随着时间依次到达的,区间的一切信息,如到达时间、区间长度、权重等在区间的到达时刻才可获知;已知区间实例集中区间的最大权重与最小权重之比为Δ;目标是确定一个工件允许被终端抢先的排序最大化接收区间的总权重。用对手法给出了该问题的一个下界为2,接着用组合分析法设计了该问题的一个在线算法H,并用最小反例法证明其竞争比分别为(1+(4Δ+1)1/2)/2(1≤Δ≤12时)和4(Δ>12时)。表明当Δ=2时,算法H是一个最好可能的在线算法.

A new environment of semi-online scheduling was introduced in which intervals arrive over time,and the characteristics of each interval such as arrive time,interval length,weight,are unknown until it is released.The ratio of the largest weight and the smallest weight is Δ and known to the online player in advance.The goal is to determine a preemptive schedule which maximizes total weight of the accepted intervals.Firstly the adversary method is used to present a lower bound 2,and then it is used the combination analysis method,smallest counterexample method to design and analysis an online algorithm H with a competitive ratio of（1 ＋（4Δ ＋1）1 /2） /2（for 1≤Δ≤12） and 4（for Δ 12）.This means that algorithm H is a best possible online algorithm for the case that Δ = 2.