A 2.28-competitive algorithm for online scheduling on identical machines

Previous Article
Sensor deployment for pipeline leakage detection via optimal boundary control strategies
JIMO Home
This Issue
Next Article
Optimization problems on the rank of the solution to left and right inverse eigenvalue problem

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

Abstract
Related Papers

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 and 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.
[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.
[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.
[4]	A. Fiat and G. J. Woeginger, Competitive analysis of algorithms, Lecture Notes in Computer Science, 1442 (1998), 1-12. doi: 10.1007/BFb0029562.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[13]	M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4nd edition, Springer-Verlag, New York, 2012. doi: 10.1007/978-1-4614-2361-4.
[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.
[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.
[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.
[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.

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.
[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.
[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.
[4]	A. Fiat and G. J. Woeginger, Competitive analysis of algorithms, Lecture Notes in Computer Science, 1442 (1998), 1-12. doi: 10.1007/BFb0029562.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[13]	M. Pinedo, Scheduling: Theory, Algorithms, and Systems, 4nd edition, Springer-Verlag, New York, 2012. doi: 10.1007/978-1-4614-2361-4.
[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.
[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.
[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.
[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.

[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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2021 doi: 10.3934/jimo.2021144

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Jiping Tao Ronghuan Huang Tundong Liu
on Google Scholar
Jiping Tao Ronghuan Huang Tundong Liu

[Back to Top]