An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time

The single machine semi-online scheduling problem is considered with the assumption that the ratio of the longest processing time to the shortest one is not greater than γ. The goal is to minimize the total weighted completion time. We design a semi-online algorithm and prove that it has a competitive ratio of , which is also shown to be the best performance achieved by any deterministic semi-online algorithm for the problem.