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

Ling Lin; Dong He; Zhiyi Tan

doi:10.3934/jimo.2008.4.817

Article Contents

2008, Volume 4, Issue 4: 817-826. Doi: 10.3934/jimo.2008.4.817

This issue Previous Article On maximizing the expected terminal utility by investment and reinsurance Next Article Supply chain partnership for Three-Echelon deteriorating inventory model

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

1.
Department of Fundamental Education, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100
2.
Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027

Received: May 2008

Revised: August 2008

Published: October 2008

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90B35, 90C27.

Citation:

Article Metrics

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

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

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

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

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content