Advanced Search
Article Contents
Article Contents

A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times

Abstract Related Papers Cited by
  • The single machine semi-online scheduling problem with the objective of minimizing total completion time is investigated with the assumption that the ratio of the longest to the shortest processing time is not greater than a constant $\gamma$. A semi-online algorithm is designed and its competitive ratio 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 and modifies the instance towards the possible structure of the worst-case instance with respect to the given online algorithm. The modification guarantees that the performance ratio does not decrease. Eventually, it comes up with a relatively simple instance with a special structure, whose performance ratio can be directly analyzed and serves as an upper bound on the competitive ratio.
    Mathematics Subject Classification: Primary: 90B35; Secondary: 68Q25.


    \begin{equation} \\ \end{equation}
  • 加载中

Article Metrics

HTML views() PDF downloads(160) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint