Journal of Industrial and Management Optimization · 2010 · 14 citations · 0 references
ComputingComputer ScienceAlgorithmsOptimizationSchedulingAlgorithm AnalysisJob SchedulingMachine SchedulingOnline AlgorithmsOnline SchedulingScheduling TheoryCompetitive RatioExpected Completion Time MinimizationExpected Time To CompletionOnline Competitive AnalysisOnline Single-machine SchedulingSingle-machine SchedulingUpper Bound Computation
The single machine semi-online scheduling problem with the objective ofminimizing total completion time is investigated with the assumption that theratio of the longest to the shortest processing time is not greater than aconstant $\gamma$. A semi-online algorithm is designed and its competitiveratio is proven to be $1+ \frac{\gamma - 1}{1 + \sqrt {1 + \gamma (\gamma -1)}}$. The competitive analysis method is as following: it starts from an arbitrary instance andmodifies the instance towards the possible structure of the worst-case instancewith respect to the given online algorithm. The modification guarantees thatthe performance ratio does not decrease. Eventually, it comes up with arelatively simple instance with a special structure, whose performance ratiocan be directly analyzed and serves as an upper bound on the competitive ratio.