A SEMI-ONLINE ALGORITHM AND ITS COMPETITIVE ANALYSIS FOR A SINGLE MACHINE SCHEDULING PROBLEM WITH BOUNDED PROCESSING TIMES

The single machine semi-online scheduling problem with the objective of minimizing total completion time is investigated with the assumption that the ratio of the longest to the shortest processing time is not greater than a constant gamma. A semi-online algorithm is designed and its competitive ratio is proven to be 1 + gamma-1/1+root 1+gamma(gamma-1). The competitive analysis method is as following: it starts from an arbitrary instance and modifies the instance towards the possible structure of the worst-case instance with respect to the given online algorithm. The modification guarantees that the performance ratio does not decrease. Eventually, it comes up with a relatively simple instance with a special structure, whose performance ratio can be directly analyzed and serves as an upper bound on the competitive ratio