`a`
Journal of Industrial and Management Optimization (JIMO)
 

An improved 2.11-competitive 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), 686-697.       
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.       
3 J. R. Correa and M. R. Wagner, LP-based online scheduling: from single to parallel machines, Mathematical Programming, 119 (2009), 109-136.       
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), 165-192.       
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), 287-326.       
6 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.       
7 T. Kawaguchi and S. Kyan, Worst case bound of an LRF schedule for the mean weighted flow-time problem, SIAM Journal on Computing, 15 (1986), 1119-1129.       
8 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.       
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), 570-583.       
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), 114-119.
11 N. Megow and A. S. Schulz, On-line scheduling to minimize average completion time revisited, Operations Research Letters, 32 (2004), 485-490.       
12 C. Phillips, C. Stein and J. Wein, Minimizing average completion time in the presence of release dates, Mathematical Programming, 82 (1998), 199-223.       
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), 411-423.       
14 W. Smith, Various optimizers for single-stage production problem, Naval Research Logistics Quarterly, 3 (1956), 59-66.       
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), 215-224.       
16 J. P. Tao, R. H. Huang and T. D. Liu, A 2.28-competitive algorithm for online scheduling on identical machines, Journal of Industrial and Management Optimization, 11 (2015), 185-198.       
17 A. P. A. Vestjens, On-line Machine Scheduling, PhD thesis, Technische Universiteit Eindhoven, Eindhoven, Netherlands, 1997.       

Go to top