آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 125 |
| تعداد مقالات | 1,580 |
| تعداد مشاهده مقاله | 1,733,008 |
| تعداد دریافت فایل اصل مقاله | 1,611,543 |
The minimum cost problem of downgrading minimum lateness scheduling under uncertainty | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 19 تیر 1404 اصل مقاله (424.55 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2025.30140.2332 | ||
| نویسندگان | ||
| Hiep Thanh Tran1، 2، 3؛ Duc Minh Phung2، 4؛ Kien Trung Nguyen* 5 | ||
| 1Department of Applied Mathematics, Faculty of Applied Sciences, Ho Chi Minh University of Technology (HCMUT), 268 Ly Thuong Kiet Street, District 10, Ho Chi Minh City, Vietnam | ||
| 2Vietnam National University Ho Chi Minh City, Linh Trung Ward, Thu Duc City, Ho Chi Minh City, Vietnam | ||
| 3Department of Mathematics, FPT University (HCM City Campus), Vietnam | ||
| 4Department of Mathematics and Physics, University of Information Technology, Ho Chi Minh City, Vietnam | ||
| 5Faculty of Mathematics and Informatics, Teacher College, Can Tho University, Can Tho, Vietnam | ||
| چکیده | ||
| The minimum lateness scheduling problem seeks to create a schedule that minimizes the largest lateness of the system. This paper deals with the challenge of increasing the processing time of jobs in a minimum cost such that the minimum lateness attains a given bound. It is called the minimum cost problem of downgrading minimum lateness scheduling. Additionally, the modifying costs are represented as intervals, and we apply the minmax regret criterion to address this uncertainty. Our contribution is an $O(n^2)$ algorithm for solving the corresponding robust problem. | ||
| کلیدواژهها | ||
| Robust optimization؛ Downgrading problem؛ Scheduling؛ Lateness | ||
| مراجع | ||
|
[1] E. Afrashteh, B. Alizadeh, and F. Baroughi, Optimal approaches for upgrading selective obnoxious p-median location problems on tree networks, Ann. Oper. Res. 289 (2020), no. 2, 153–172. https://doi.org/10.1007/s10479-020-03561-4
[2] H. Aissi, C. Bazgan, and D. Vanderpooten, Min–max and min–max regret versions of combinatorial optimization problems: A survey, European J. Oper. Res. 197 (2009), no. 2, 427–438. https://doi.org/10.1016/j.ejor.2008.09.012
[3] L.Q. Anh, H.M. Le, K.T. Nguyen, and L.X. Thanh, An algorithmic approach to the robust downgrading makespan scheduling problem, Appl. Set-Valued Anal. Optim 6 (2024), no. 3, 263–273. https://doi.org/10.23952/asvao.6.2024.3.02
[4] I. Averbakh, Minmax regret linear resource allocation problems, Oper. Res. Lett. 32 (2004), no. 2, 174–180. https://doi.org/10.1016/S0167-6377(03)00091-9
[5] O. Bachtler, S.O. Krumke, and H. Minh Le, Robust single machine makespan scheduling with release date uncertainty, Oper. Res. Lett. 48 (2020), no. 6, 816–819. https://doi.org/10.1016/j.orl.2020.10.003
[6] M. Baldomero-Naranjo, J. Kalcsics, A. Mar´ın, and A.M. Rodríguez-Chía, Upgrading edges in the maximal covering location problem, European J. Oper. Res. 303 (2022), no. 1, 14–36. https://doi.org/10.1016/j.ejor.2022.02.001
[7] A. Ben-Tal, L.E. Ghaoui, and A. Nemirovski, Robust Optimization, Princeton University Press, Princeton, New Jersey, 2009.
[8] P. Brucker, Scheduling Algorithms (fifth edition), Springer Verlag, Heidelberg, 2007.
[9] Rainer E Burkard, Bettina Klinz, and Jianzhong Zhang, Bottleneck capacity expansion problems with general budget constraints, RAIRO Oper. Res. 35 (2001), no. 1, 1–20. https://doi.org/10.1051/ro:2001100
[10] Rainer E Burkard, Yixun Lin, and Jianzhong Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res. 153 (2004), no. 1, 191– 199. https://doi.org/10.1016/S0377-2217(02)00713-0
[11] K.U. Drangmeister, S.O. Krurnke, M.V. Marathe, H. Noltemeier, and S.S. Ravi, Modifying edges of a network to obtain short subgraphs, Theor. Comput. Sci. 203 (1998), no. 1, 91–121. https://doi.org/10.1016/S0304-3975(97)00290-9
[12] G.N. Frederickson and R. Solis-Oba, Increasing the weight of minimum spanning trees, J. Algorithms. 33 (1999), no. 2, 244–266. https://doi.org/10.1006/jagm.1999.1026
[13] D.R. Fulkerson and G.C. Harding, Maximizing the minimum source-sink path subject to a budget constraint, Math. Program. 13 (1977), no. 1, 116–118. https://doi.org/10.1007/BF01584329
[14] E. Gassner, A game-theoretic approach for downgrading the 1-median in the plane with Manhattan metric, Ann. Oper. Res. 172 (2009), no. 1, 393–404. https://doi.org/10.1007/s10479-009-0641-1
[15] E. Gassner, Up-and downgrading the 1-center in a network, European J. Oper. Res. 198 (2009), no. 2, 370–377. https://doi.org/10.1016/j.ejor.2008.09.013
[16] P. Kouvelis and G. Yu, Robust Discrete Optimization and Its Applications, Springer Science & Business Media, 2013.
[17] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, vol. 4, Elsevier, 1993, pp. 445–522. https://doi.org/10.1016/S0927-0507(05)80189-6
[18] J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math., vol. 1, Elsevier, 1977, pp. 343–362. https://doi.org/10.1016/S0167-5060(08)70743-X
[19] K.T. Nguyen and N.T. Hung, The minmax regret inverse maximum weight problem, Appl. Math. Comput. 407 (2021), Article ID: 126328. https://doi.org/10.1016/j.amc.2021.126328
[20] T.H.N. Nhan, K.T. Nguyen, and H. Nguyen-Thu, The minmax regret reverse 1-median problem on trees with uncertain vertex weights, Asia-Pac. J. Oper. Res. 40 (2023), no. 3, Article ID: 2250033. https://doi.org/10.1142/S0217595922500336
[21] M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer New York, 2012.
[22] F. Plastria, Up-and downgrading the euclidean 1-median problem and knapsack Voronoi diagrams, Ann. Oper. Res. 246 (2016), no. 1, 227–251. https://doi.org/10.1007/s10479-014-1587-5
[23] A.R. Sepasian, Upgrading the 1-center problem with edge length variables on a tree, Discrete Optim. 29 (2018), 1–17. https://doi.org/10.1016/j.disopt.2018.02.002 [24] A.R. Sepasian and E. Monabbati, Upgrading min–max spanning tree problem under various cost functions, Theor. Comput. Sci. 704 (2017), 87–91. https://doi.org/10.1016/j.tcs.2017.08.006
[25] H. Xiong, S. Shi, D. Ren, and J. Hu, A survey of job shop scheduling problem: The types and models, Comput. Oper. Res. 142 (2022), Article ID: 105731. https://doi.org/10.1016/j.cor.2022.105731 | ||
|
آمار تعداد مشاهده مقاله: 258 تعداد دریافت فایل اصل مقاله: 174 |
||