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 @c. 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 [email protected]^[email protected], which is also shown to be the best performance achieved by any deterministic semi-online algorithm for the problem.