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 gamma. 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 1 + root 4 gamma(2)+1-1/2 gamma, which is also shown to be the best performance achieved by any deterministic semi-online algorithm for the problem. (C) 2010 Elsevier B.V. All rights reserved.
semi-online algorithms single machine scheduling total weighted completion time competitive ratio analysis of algorithms