-
Previous Article
Sensor deployment for pipeline leakage detection via optimal boundary control strategies
- JIMO Home
- This Issue
-
Next Article
Optimization problems on the rank of the solution to left and right inverse eigenvalue problem
A $2.28$-competitive algorithm for online scheduling on identical machines
1. | Department of Automation, Xiamen University, 422 South Siming Road, Xiamen, 361005, China, China, China |
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. |
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-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. |
[1] |
Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057 |
[2] |
Jiping Tao, Zhijun Chao, Yugeng 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, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 |
[3] |
P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95 |
[4] |
Ling Lin, Dong He, Zhiyi Tan. Bounds on delay start LPT algorithm for scheduling on two identical machines in the $l_p$ norm. Journal of Industrial and Management Optimization, 2008, 4 (4) : 817-826. doi: 10.3934/jimo.2008.4.817 |
[5] |
Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008 |
[6] |
Lili Ding, Xinmin Liu, Yinfeng Xu. Competitive risk management for online Bahncard problem. Journal of Industrial and Management Optimization, 2010, 6 (1) : 1-14. doi: 10.3934/jimo.2010.6.1 |
[7] |
Ruinian Li, Yinhao Xiao, Cheng Zhang, Tianyi Song, Chunqiang Hu. Cryptographic algorithms for privacy-preserving online applications. Mathematical Foundations of Computing, 2018, 1 (4) : 311-330. doi: 10.3934/mfc.2018015 |
[8] |
M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial and Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445 |
[9] |
Zhao-Hong Jia, Ting-Ting Wen, Joseph Y.-T. Leung, Kai Li. Effective heuristics for makespan minimization in parallel batch machines with non-identical capacities and job release times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 977-993. doi: 10.3934/jimo.2016057 |
[10] |
Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022 |
[11] |
Xianzhao Zhang, Dachuan Xu, Donglei Du, Cuixia Miao. Approximate algorithms for unrelated machine scheduling to minimize makespan. Journal of Industrial and Management Optimization, 2016, 12 (2) : 771-779. doi: 10.3934/jimo.2016.12.771 |
[12] |
Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021124 |
[13] |
Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete and Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1 |
[14] |
Donglei Du, Xiaoyue Jiang, Guochuan Zhang. Optimal preemptive online scheduling to minimize lp norm on two processors. Journal of Industrial and Management Optimization, 2005, 1 (3) : 345-351. doi: 10.3934/jimo.2005.1.345 |
[15] |
Zhenhuan Yang, Yiming Ying, Qilong Min. Online optimization for residential PV-ESS energy system scheduling. Mathematical Foundations of Computing, 2019, 2 (1) : 55-71. doi: 10.3934/mfc.2019005 |
[16] |
Matthew M. Dunlop, Andrew M. Stuart. The Bayesian formulation of EIT: Analysis and algorithms. Inverse Problems and Imaging, 2016, 10 (4) : 1007-1036. doi: 10.3934/ipi.2016030 |
[17] |
Hua-Ping Wu, Min Huang, W. H. Ip, Qun-Lin Fan. Algorithms for single-machine scheduling problem with deterioration depending on a novel model. Journal of Industrial and Management Optimization, 2017, 13 (2) : 681-695. doi: 10.3934/jimo.2016040 |
[18] |
Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial and Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253 |
[19] |
Jun Fan, Dao-Hong Xiang. Quantitative convergence analysis of kernel based large-margin unified machines. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4069-4083. doi: 10.3934/cpaa.2020180 |
[20] |
Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021144 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]