Advanced Search
Article Contents
Article Contents

Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm

Abstract Related Papers Cited by
  • In this paper, we consider the scheduling problem on two identical machines with objective to minimize the sum of the $l_{p}$ norm of every machine's load. We present the worst-case ratio of $DSL(l)$ for any integer $l$, here $DSL(l)$ first assigns the $l-1$ largest jobs optimally, then assigns the remaining jobs by $LS$ rule. It follows that $DSL(l)$ is an all-norm $\frac{l+2}{l+1}$ -approximation algorithm. Improved tight bound is given for $l=7$ in the $l_{2}$ norm.
    Mathematics Subject Classification: 90B35, 90C27.


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

Article Metrics

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

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint