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

Jian Yang, Bendong Lou. Traveling wave solutions of competitive models with free boundaries. Discrete & Continuous Dynamical Systems - B, 2014, 19 (3) : 817-826. doi: 10.3934/dcdsb.2014.19.817
[2]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389
[3]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1
[4]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[5]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027
[6]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037
[7]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024
[8]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[9]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[10]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[11]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[12]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[13]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[14]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[15]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[16]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[17]

Xiaoyi Zhou, Tong Ye, Tony T. Lee. Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021038
[18]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences