July  2005, 1(3): 345-351. doi: 10.3934/jimo.2005.1.345

Optimal preemptive online scheduling to minimize lp norm on two processors

1. 

Faculty of Business Administration, University of New Brunswick, P.O.Box 4400, Fredericton, NB E3B 5A3, Canada

2. 

College of Engineering, Louisiana State University, Baton Rouge, LA 70803, United States

3. 

Department of Mathematics, Zhejiang University, Hangzhou 310027, PR, China

Received  August 2004 Revised  January 2005 Published  July 2005

We consider an on-line scheduling problem, where jobs arrive one by one to be scheduled on two identical parallel processors with preemption. The objective is to minimize the machine completion time vector with respect to the $l_p$ norm. We present a best possible deterministic on-line scheduling algorithm along with a matching lower bound.
Citation: 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
[1]

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

[2]

Danthai Thongphiew, Vira Chankong, Fang-Fang Yin, Q. Jackie Wu. An on-line adaptive radiation therapy system for intensity modulated radiation therapy: An application of multi-objective optimization. Journal of Industrial & Management Optimization, 2008, 4 (3) : 453-475. doi: 10.3934/jimo.2008.4.453

[3]

Elena Beretta, Markus Grasmair, Monika Muszkieta, Otmar Scherzer. A variational algorithm for the detection of line segments. Inverse Problems & Imaging, 2014, 8 (2) : 389-408. doi: 10.3934/ipi.2014.8.389

[4]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[5]

Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391

[6]

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

[7]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[8]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[9]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[10]

Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

[11]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030

[12]

Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088

[13]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019122

[14]

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

[15]

Sun-Sig Byun, Hongbin Chen, Mijoung Kim, Lihe Wang. Lp regularity theory for linear elliptic systems. Discrete & Continuous Dynamical Systems - A, 2007, 18 (1) : 121-134. doi: 10.3934/dcds.2007.18.121

[16]

Yanni Zeng. LP decay for general hyperbolic-parabolic systems of balance laws. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 363-396. doi: 10.3934/dcds.2018018

[17]

Markus Kunze, Abdallah Maichine, Abdelaziz Rhandi. Vector-valued Schrödinger operators in Lp-spaces. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1-13. doi: 10.3934/dcdss.2020086

[18]

Baolin He. Entropy of diffeomorphisms of line. Discrete & Continuous Dynamical Systems - A, 2017, 37 (9) : 4753-4766. doi: 10.3934/dcds.2017204

[19]

Yuzhong Zhang, Chunsong Bai, Qingguo Bai, Jianteng Xu. Duplicating in batch scheduling. Journal of Industrial & Management Optimization, 2007, 3 (4) : 685-692. doi: 10.3934/jimo.2007.3.685

[20]

N. V. Krylov. Uniqueness for Lp-viscosity solutions for uniformly parabolic Isaacs equations with measurable lower order terms. Communications on Pure & Applied Analysis, 2018, 17 (6) : 2495-2516. doi: 10.3934/cpaa.2018119

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]