January  2015, 11(1): 185-198. doi: 10.3934/jimo.2015.11.185

A $2.28$-competitive algorithm for online scheduling on identical machines

1. 

Department of Automation, Xiamen University, 422 South Siming Road, Xiamen, 361005, China, China, China

Received  March 2013 Revised  January 2014 Published  May 2014

Online scheduling on identical machines is investigated in the setting where jobs arrive over time. The goal is to minimize the total completion time. A waiting strategy based online algorithm is designed and is proved to be $2.28$-competitive. The result improves the current best online algorithm from the worse-case prospective.
Citation: 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
References:
[1]

E. J. Anderson and C. N. Potts, Online scheduling of a single machine to minimize total weighted completion time,, Mathematics of Operations Research, 29 (2004), 686. doi: 10.1287/moor.1040.0092. Google Scholar

[2]

M. C. Chou, M. Queyranne and D. Simchi-Levi, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates,, Mathematical Programming, 106 (2006), 137. doi: 10.1007/s10107-005-0588-1. Google Scholar

[3]

J. R. Correa and M. R. Wagner, LP-based online scheduling: From single to parallel machines,, Mathematical Programming, 119 (2009), 109. doi: 10.1007/s10107-007-0204-7. Google Scholar

[4]

A. Fiat and G. J. Woeginger, Competitive analysis of algorithms,, Lecture Notes in Computer Science, 1442 (1998), 1. doi: 10.1007/BFb0029562. Google Scholar

[5]

M. X. Goemans, Improved approximation algorithms for scheduling with release dates,, in Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, (1997), 591. Google Scholar

[6]

M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella and Y. Wang, Single machine scheduling with release dates,, SIAM Journal on Discrete Mathematics, 15 (2002), 165. doi: 10.1137/S089548019936223X. Google Scholar

[7]

L. A. Hall, A. S. Schulz, D. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms,, Mathematics of Operations Research, 22 (1997), 513. doi: 10.1287/moor.22.3.513. Google Scholar

[8]

J. A. Hoogeveen and A. P. A. Vestjens, Optimal on-line algorithms for single-machine scheduling,, Lecture Notes in Computer Science, 1084 (1996), 404. doi: 10.1007/3-540-61310-2_30. Google Scholar

[9]

P. H. Liu and X. W. Lu, On-line scheduling of parallel machines to minimize total completion times,, Computers & Operations Research, 36 (2009), 2647. doi: 10.1016/j.cor.2008.11.008. Google Scholar

[10]

X. Lu, R. A. Sitters and L. Stougie, A class of on-line scheduling algorithms to minimize total completion time,, Operations Research Letters, 31 (2003), 232. doi: 10.1016/S0167-6377(03)00016-6. Google Scholar

[11]

N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited,, Operations Research Letters, 32 (2004), 485. doi: 10.1016/j.orl.2003.11.008. Google Scholar

[12]

C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates,, Mathematical Programming, 82 (1998), 199. doi: 10.1007/BF01585872. Google Scholar

[13]

M. Pinedo, Scheduling: Theory, Algorithms, and Systems,, 4nd edition, (2012). doi: 10.1007/978-1-4614-2361-4. Google Scholar

[14]

R. Sitters, Efficient algorithms for average completion time scheduling,, Lecture Notes in Computer Science, 6080 (2010), 411. doi: 10.1007/978-3-642-13036-6_31. Google Scholar

[15]

J. P. Tao, H. Jiang and T. D. Liu, A 2.5-competitive Online Algorithm for $P_m|r_j|\sum w_jC_j$,, in the 24th Chinese Control and Decision Conference (CCDC), (2012), 3184. Google Scholar

[16]

J. P. Tao, Z. J. Chao and Y. G. Xi, A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times,, Journal of Industrial and Management Optimization, 6 (2010), 269. doi: 10.3934/jimo.2010.6.269. Google Scholar

[17]

J. P. Tao, Z. J. Chao, Y. G. Xi and Y. Tao, An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time,, Information Processing Letters, 110 (2010), 325. doi: 10.1016/j.ipl.2010.02.013. Google Scholar

show all references

References:
[1]

E. J. Anderson and C. N. Potts, Online scheduling of a single machine to minimize total weighted completion time,, Mathematics of Operations Research, 29 (2004), 686. doi: 10.1287/moor.1040.0092. Google Scholar

[2]

M. C. Chou, M. Queyranne and D. Simchi-Levi, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates,, Mathematical Programming, 106 (2006), 137. doi: 10.1007/s10107-005-0588-1. Google Scholar

[3]

J. R. Correa and M. R. Wagner, LP-based online scheduling: From single to parallel machines,, Mathematical Programming, 119 (2009), 109. doi: 10.1007/s10107-007-0204-7. Google Scholar

[4]

A. Fiat and G. J. Woeginger, Competitive analysis of algorithms,, Lecture Notes in Computer Science, 1442 (1998), 1. doi: 10.1007/BFb0029562. Google Scholar

[5]

M. X. Goemans, Improved approximation algorithms for scheduling with release dates,, in Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, (1997), 591. Google Scholar

[6]

M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella and Y. Wang, Single machine scheduling with release dates,, SIAM Journal on Discrete Mathematics, 15 (2002), 165. doi: 10.1137/S089548019936223X. Google Scholar

[7]

L. A. Hall, A. S. Schulz, D. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Off-line and on-line approximation algorithms,, Mathematics of Operations Research, 22 (1997), 513. doi: 10.1287/moor.22.3.513. Google Scholar

[8]

J. A. Hoogeveen and A. P. A. Vestjens, Optimal on-line algorithms for single-machine scheduling,, Lecture Notes in Computer Science, 1084 (1996), 404. doi: 10.1007/3-540-61310-2_30. Google Scholar

[9]

P. H. Liu and X. W. Lu, On-line scheduling of parallel machines to minimize total completion times,, Computers & Operations Research, 36 (2009), 2647. doi: 10.1016/j.cor.2008.11.008. Google Scholar

[10]

X. Lu, R. A. Sitters and L. Stougie, A class of on-line scheduling algorithms to minimize total completion time,, Operations Research Letters, 31 (2003), 232. doi: 10.1016/S0167-6377(03)00016-6. Google Scholar

[11]

N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited,, Operations Research Letters, 32 (2004), 485. doi: 10.1016/j.orl.2003.11.008. Google Scholar

[12]

C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates,, Mathematical Programming, 82 (1998), 199. doi: 10.1007/BF01585872. Google Scholar

[13]

M. Pinedo, Scheduling: Theory, Algorithms, and Systems,, 4nd edition, (2012). doi: 10.1007/978-1-4614-2361-4. Google Scholar

[14]

R. Sitters, Efficient algorithms for average completion time scheduling,, Lecture Notes in Computer Science, 6080 (2010), 411. doi: 10.1007/978-3-642-13036-6_31. Google Scholar

[15]

J. P. Tao, H. Jiang and T. D. Liu, A 2.5-competitive Online Algorithm for $P_m|r_j|\sum w_jC_j$,, in the 24th Chinese Control and Decision Conference (CCDC), (2012), 3184. Google Scholar

[16]

J. P. Tao, Z. J. Chao and Y. G. Xi, A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times,, Journal of Industrial and Management Optimization, 6 (2010), 269. doi: 10.3934/jimo.2010.6.269. Google Scholar

[17]

J. P. Tao, Z. J. Chao, Y. G. Xi and Y. Tao, An optimal semi-online algorithm for a single machine scheduling problem with bounded processing time,, Information Processing Letters, 110 (2010), 325. doi: 10.1016/j.ipl.2010.02.013. Google Scholar

[1]

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

[2]

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

[3]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial & Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[4]

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

[5]

Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008

[6]

Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial & Management Optimization, 2010, 6 (1) : 1-14. doi: 10.3934/jimo.2010.6.1

[7]

Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015

[8]

M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445

[9]

Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057

[10]

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

[11]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1

[12]

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

[13]

Zhenhuan Yang, Yiming Ying, Qilong Min. Online optimization for residential PV-ESS energy system scheduling. Mathematical Foundations of Computing, 2019, 2 (1) : 55-71. doi: 10.3934/mfc.2019005

[14]

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

[15]

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

[16]

Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253

[17]

Yong Zhang, Francis Y. L. Chin, Francis C. M. Lau, Haisheng Tan, Hing-Fung Ting. Constant competitive algorithms for unbounded one-Way trading under monotone hazard rate. Mathematical Foundations of Computing, 2018, 1 (4) : 383-392. doi: 10.3934/mfc.2018019

[18]

Pengyu Yan, Shi Qiang Liu, Cheng-Hu Yang, Mahmoud Masoud. A comparative study on three graph-based constructive algorithms for multi-stage scheduling with blocking. Journal of Industrial & Management Optimization, 2019, 15 (1) : 221-233. doi: 10.3934/jimo.2018040

[19]

Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867

[20]

Jian Xiong, Yingwu Chen, Zhongbao Zhou. Resilience analysis for project scheduling with renewable resource constraint and uncertain activity durations. Journal of Industrial & Management Optimization, 2016, 12 (2) : 719-737. doi: 10.3934/jimo.2016.12.719

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (9)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]