-
Previous Article
VISUAL MISER: An efficient user-friendly visual program for solving optimal control problems
- JIMO Home
- This Issue
-
Next Article
The coordination of single-machine scheduling with availability constraints and delivery
Approximate algorithms for unrelated machine scheduling to minimize makespan
1. | School of Science, Linyi University, Linyi 276005, China |
2. | Department of Information and Operations Research, Beijing University of Technology, Beijing 100124, China |
3. | Faculty of Business Administration, University of New Brunswick, Fredericton, NB, E3B 5A3 |
4. | School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China |
References:
[1] |
L. Chen, W. C. Luo, and G. C. Zhang, Approximation algorithms for unrelated machine scheduling with an energy budget, in Proceedings of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), (2011), 244-254.
doi: 10.1007/978-3-642-21204-8_27. |
[2] |
J. R. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, and J. Verschae, Strong LP formulations for scheduling splittable jobs on unrelated machines, in Proceedings of the 17th Integer Programming and Combinatorial Optimization (IPCO), (2014), 249-260.
doi: 10.1007/978-3-319-07557-0_21. |
[3] |
T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing: a special case of scheduling unrelated parallel machines, Algorithmica, 68 (2014), 62-80.
doi: 10.1007/s00453-012-9668-9. |
[4] |
N. K. Freemana, J. Mittenthala and S. H. Melouk, Parallel-machine scheduling to minimize overtime and waste costs, IIE Transactions, 46 (2014), 601-618.
doi: 10.1080/0740817X.2013.851432. |
[5] |
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.
doi: 10.1016/S0167-5060(08)70356-X. |
[6] |
A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times, Mathematical Programming, 110 (2007), 209-228.
doi: 10.1007/s10107-006-0059-3. |
[7] |
J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46 (1990), 259-271.
doi: 10.1007/BF01585745. |
[8] |
W. Li, J. Li, X. Zhang and Z. Chen, Parallel-machine scheduling problem under the job rejection constraint, in Proceedings of the 8th Frontiers in Algorithmics (FAW), (2014), 158-169.
doi: 10.1007/978-3-319-08016-1_15. |
[9] |
E. V. Shchepin and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines, Operational Research Letters, 33 (2005), 127-133.
doi: 10.1016/j.orl.2004.05.004. |
[10] |
D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming, 62 (1993), 461-474.
doi: 10.1007/BF01585178. |
[11] |
O. Svensson, Santa clause schedules jobs on unrelated machines, SIAM Journal on Computing, 41 (2012), 1318-1341.
doi: 10.1137/110851201. |
[12] |
V. V. Vazirani, Approximation Algorithms, Springer, Berlin, 2003. |
[13] |
D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, London, 2011.
doi: 10.1017/CBO9780511921735. |
show all references
References:
[1] |
L. Chen, W. C. Luo, and G. C. Zhang, Approximation algorithms for unrelated machine scheduling with an energy budget, in Proceedings of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), (2011), 244-254.
doi: 10.1007/978-3-642-21204-8_27. |
[2] |
J. R. Correa, A. Marchetti-Spaccamela, J. Matuschke, L. Stougie, O. Svensson, V. Verdugo, and J. Verschae, Strong LP formulations for scheduling splittable jobs on unrelated machines, in Proceedings of the 17th Integer Programming and Combinatorial Optimization (IPCO), (2014), 249-260.
doi: 10.1007/978-3-319-07557-0_21. |
[3] |
T. Ebenlendr, M. Krcal, and J. Sgall, Graph balancing: a special case of scheduling unrelated parallel machines, Algorithmica, 68 (2014), 62-80.
doi: 10.1007/s00453-012-9668-9. |
[4] |
N. K. Freemana, J. Mittenthala and S. H. Melouk, Parallel-machine scheduling to minimize overtime and waste costs, IIE Transactions, 46 (2014), 601-618.
doi: 10.1080/0740817X.2013.851432. |
[5] |
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.
doi: 10.1016/S0167-5060(08)70356-X. |
[6] |
A. Grigoriev, M. Sviridenko and M. Uetz, Machine scheduling with resource dependent processing times, Mathematical Programming, 110 (2007), 209-228.
doi: 10.1007/s10107-006-0059-3. |
[7] |
J. K. Lenstra, D. B. Shmoys and É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming, 46 (1990), 259-271.
doi: 10.1007/BF01585745. |
[8] |
W. Li, J. Li, X. Zhang and Z. Chen, Parallel-machine scheduling problem under the job rejection constraint, in Proceedings of the 8th Frontiers in Algorithmics (FAW), (2014), 158-169.
doi: 10.1007/978-3-319-08016-1_15. |
[9] |
E. V. Shchepin and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines, Operational Research Letters, 33 (2005), 127-133.
doi: 10.1016/j.orl.2004.05.004. |
[10] |
D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming, 62 (1993), 461-474.
doi: 10.1007/BF01585178. |
[11] |
O. Svensson, Santa clause schedules jobs on unrelated machines, SIAM Journal on Computing, 41 (2012), 1318-1341.
doi: 10.1137/110851201. |
[12] |
V. V. Vazirani, Approximation Algorithms, Springer, Berlin, 2003. |
[13] |
D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, London, 2011.
doi: 10.1017/CBO9780511921735. |
[1] |
Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control and Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115 |
[2] |
Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021190 |
[3] |
Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259 |
[4] |
Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174 |
[5] |
Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613 |
[6] |
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 |
[7] |
Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial and Management Optimization, 2019, 15 (2) : 577-593. doi: 10.3934/jimo.2018058 |
[8] |
Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 |
[9] |
Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017 |
[10] |
Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial and Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271 |
[11] |
Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243 |
[12] |
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 |
[13] |
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 |
[14] |
Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323 |
[15] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[16] |
Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032 |
[17] |
Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009 |
[18] |
Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132 |
[19] |
Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial and Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 |
[20] |
Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]