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

Jiping Tao; Ronghuan Huang; Tundong Liu

doi:10.3934/jimo.2015.11.185

Article Contents

2015, Volume 11, Issue 1: 185-198. Doi: 10.3934/jimo.2015.11.185

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

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

1.
Department of Automation, Xiamen University, 422 South Siming Road, Xiamen, 361005

Received: March 2013

Revised: January 2014

Published: January 2015

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90B35; Secondary: 68Q25.

Citation:

Related Papers

Cited by

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.