The minimum cost problem of downgrading minimum lateness scheduling under uncertainty

Articles in Press

Document Type : Original paper

Authors

1 Department 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

2 Vietnam National University Ho Chi Minh City, Linh Trung Ward, Thu Duc City, Ho Chi Minh City, Vietnam

3 Department of Mathematics, FPT University (HCM City Campus), Vietnam

4 Department of Mathematics and Physics, University of Information Technology, Ho Chi Minh City, Vietnam

5 Faculty of Mathematics and Informatics, Teacher College, Can Tho University, Can Tho, Vietnam

Abstract

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(n2) algorithm for solving the corresponding robust problem.

Keywords

Main Subjects

References

[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
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 10 July 2025

Files

Share

How to cite

Statistics