Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90B35; Secondary: 68Q25.

 Citation:

•  [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.