American Institute of Mathematical Sciences

Advanced
October  2008, 4(4): 817-826. doi: 10.3934/jimo.2008.4.817

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

Ling Lin 1, , Dong He 2, and  Zhiyi Tan 2,

1. 

Department of Fundamental Education, Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China
2. 

Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, China, China

Received  May 2008 Revised  August 2008 Published  November 2008

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: $l_p$ norm., parallel machine, design and analysis of algorithms, Scheduling.
Mathematics Subject Classification: 90B35, 90C2.
Citation: Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial & Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817
[1]

Peter Weidemaier. Maximal regularity for parabolic equations with inhomogeneous boundary conditions in Sobolev spaces with mixed $L_p$-norm. Electronic Research Announcements, 2002, 8: 47-51.

[2]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[3]

Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial & Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771
[4]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial & Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[5]

Mathias Wilke. $L_p$-theory for a Cahn-Hilliard-Gurtin system. Evolution Equations & Control Theory, 2012, 1 (2) : 393-429. doi: 10.3934/eect.2012.1.393
[6]

Jian Lu, Huaiyu Jian. Topological degree method for the rotationally symmetric $L_p$-Minkowski problem. Discrete & Continuous Dynamical Systems - A, 2016, 36 (2) : 971-980. doi: 10.3934/dcds.2016.36.971
[7]

Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial & Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040
[8]

Karina Samvelyan, Frol Zapolsky. Rigidity of the ${{L}^{p}}$-norm of the Poisson bracket on surfaces. Electronic Research Announcements, 2017, 24: 28-37. doi: 10.3934/era.2017.24.004
[9]

Donglei Du, Tianping Shuai. Errata to:''Optimal preemptive online scheduling to minimize $l_{p}$ norm on two processors''[Journal of Industrial and Management Optimization, 1(3) (2005), 345-351.]. Journal of Industrial & Management Optimization, 2008, 4 (2) : 339-341. doi: 10.3934/jimo.2008.4.339
[10]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[11]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017
[12]

Stefan Meyer, Mathias Wilke. Global well-posedness and exponential stability for Kuznetsov's equation in $L_p$-spaces. Evolution Equations & Control Theory, 2013, 2 (2) : 365-378. doi: 10.3934/eect.2013.2.365
[13]

Kyeong-Hun Kim, Kijung Lee. A weighted $L_p$-theory for second-order parabolic and elliptic partial differential systems on a half space. Communications on Pure & Applied Analysis, 2016, 15 (3) : 761-794. doi: 10.3934/cpaa.2016.15.761
[14]

Ildoo Kim. An $L_p$-Lipschitz theory for parabolic equations with time measurable pseudo-differential operators. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2751-2771. doi: 10.3934/cpaa.2018130
[15]

Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[16]

Guozhen Lu, Yunyan Yang. Sharp constant and extremal function for the improved Moser-Trudinger inequality involving $L^p$ norm in two dimension. Discrete & Continuous Dynamical Systems - A, 2009, 25 (3) : 963-979. doi: 10.3934/dcds.2009.25.963
[17]

Yang Woo Shin, Dug Hee Moon. Throughput of flow lines with unreliable parallel-machine workstations and blocking. Journal of Industrial & Management Optimization, 2017, 13 (2) : 901-916. doi: 10.3934/jimo.2016052
[18]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[19]

Donglei Du, Xiaoyue Jiang, Guochuan Zhang. Optimal preemptive online scheduling to minimize lp norm on two processors. Journal of Industrial & Management Optimization, 2005, 1 (3) : 345-351. doi: 10.3934/jimo.2005.1.345
[20]

Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems & Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (8)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences