Minimizing the total completion time for a class of semi-online single machine scheduling problems
Article : Articles dans des revues internationales ou nationales avec comité de lecture
Semi-online single machine scheduling problems with information on jobs’ processing times and the objective to minimize the total completion time are considered. In these problems, a set of jobs arriving over time are to be scheduled on a single machine and their characteristics become known only upon arrival. Some of the studied problems are shown to have the same competitive ratio as the online problem and online scheduling algorithms can be applied. Given some constraints on the processing times of successive jobs, new lower bounds can be achieved and a new semi-online algorithm, called D-SPT, is presented along with its competitive analysis