American Institute of Mathematical Sciences

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

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

Jiping Tao 1, , Ronghuan Huang 1, and  Tundong Liu 1,

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.
Keywords: competitive analysis, Identical machines scheduling, online algorithms, instance reduction..
Mathematics Subject Classification: Primary: 90B35; Secondary: 68Q2.
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-697. 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-157. 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-136. 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-12. 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, New Orleans, (1997), 591-598.  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-192. 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-544. 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-414. 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-2652. 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-236. 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-490. 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-213. doi: 10.1007/BF01585872.  Google Scholar

[13]

M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4nd edition, Springer-Verlag, New York, 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-423. 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), Taiyuan, China, IEEE, (2012), 3184-3188. 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-282. 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-330. 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-697. 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-157. 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-136. 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-12. 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, New Orleans, (1997), 591-598.  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-192. 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-544. 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-414. 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-2652. 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-236. 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-490. 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-213. doi: 10.1007/BF01585872.  Google Scholar

[13]

M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4nd edition, Springer-Verlag, New York, 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-423. 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), Taiyuan, China, IEEE, (2012), 3184-3188. 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-282. 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-330. 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]

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

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

Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022
[11]

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

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

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

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

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

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

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

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

Jun Fan, Dao-Hong Xiang. Quantitative convergence analysis of kernel based large-margin unified machines. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4069-4083. doi: 10.3934/cpaa.2020180
[20]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021144

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (110)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy