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]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174
[4]

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
[5]

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
[6]

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
[7]

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

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
[9]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021124
[10]

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
[11]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021190
[18]

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
[19]

Xuerui Gao, Yanqin Bai, Shu-Cherng Fang, Jian Luo, Qian Li. A new hybrid $ l_p $-$ l_2 $ model for sparse solutions with applications to image processing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021211
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy