Abstract：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.

Keyword：online scheduling;online algorithm;equal-length intervals;competitive ratio;