An improved 2.11competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time
Page number are going to be assigned later
2017
doi:10.3934/jimo.2017057 Abstract
References
Full text (356.5K)
Ran Ma  School of Mathematics and Information Science, Henan Polytechnic University, Jiaozuo, 454000, China (email)
Jiping Tao  Department of Automation, Xiamen University, 422 South Siming Road, Xiamen, 361005, China (email)
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), 686697. 

2 
M. C. Chou, M. Queyranne and D. SimchiLevi, The asymptotic performance ratio of an online algorithm for uniform parallel machine scheduling with release dates, Mathematical Programming, 106 (2006), 137157. 

3 
J. R. Correa and M. R. Wagner, LPbased online scheduling: from single to parallel machines, Mathematical Programming, 119 (2009), 109136. 

4 
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), 165192. 

5 
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287326. 

6 
L. A. Hall, A. S. Schulz, D. B. Shmoys and J. Wein, Scheduling to minimize average completion time: Offline and online approximation algorithms, Mathematics of Operations Research, 22 (1997), 513544. 

7 
T. Kawaguchi and S. Kyan, Worst case bound of an LRF schedule for the mean weighted flowtime problem, SIAM Journal on Computing, 15 (1986), 11191129. 

8 
P. H. Liu and X. W. Lu, Online scheduling of parallel machines to minimize total completion times, Computers & Operations Research, 36 (2009), 26472652. 

9 
R. Ma, J. P. Tao and J. J. Yuan, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Applied Mathematics And Computation, 273 (2016), 570583. 

10 
R. Ma and J. J. Yuan, Online tradeoff scheduling on a single machine to minimize makespan and total weighted completion time, International Journal of Production Economics, 158 (2014), 114119. 

11 
N. Megow and A. S. Schulz, Online scheduling to minimize average completion time revisited, Operations Research Letters, 32 (2004), 485490. 

12 
C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199223. 

13 
R. Sitters, Efficient algorithms for average completion time scheduling, in Integer Programming and Combinatorial Optimization (eds. F. Eisenbrand and F. Shepherd), vol. 6080 of Lecture Notes in Computer Science, Springer, (2010), 411423. 

14 
W. Smith, Various optimizers for singlestage production problem, Naval Research Logistics Quarterly, 3 (1956), 5966. 

15 
J. P. Tao, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Computers & Operations Research, 43 (2014), 215224. 

16 
J. P. Tao, R. H. Huang and T. D. Liu, A 2.28competitive algorithm for online scheduling on identical machines, Journal of Industrial and Management Optimization, 11 (2015), 185198. 

17 
A. P. A. Vestjens, Online Machine Scheduling, PhD thesis, Technische Universiteit Eindhoven, Eindhoven, Netherlands, 1997. 

Go to top
