New ideas in Lagrangian relaxation for a scheduling problem with the weighted tardiness criterion

Rudy, Jarosław  ; Idzikowski, Radosław ; Smutnicki, Czesław ; Banaszak, Zbigniew ; Bocewicz, Grzegorz

International Journal of Applied Mathematics and Computer Science, Tome 34 (2024) no. 2, pp. 235-251.

Résumé

We consider an extension of Lagrangian relaxation methods for solving the total weighted tardiness scheduling problem on a single machine. First, we investigate a straightforward relaxation method and decompose it into upper and lower subproblems. For the upper subproblem we propose an alternative solving method in the form of a local search metaheuristic. We also introduce a scaling technique by arbitrary numbers to reduce the complexity of the problem and confront it with greatest common divisor scaling. Next, we propose a novel alternative relaxation approach based on aggregating constraints. We discuss the properties and implementation of this new approach and a technique to further reduce its computational complexity. We perform a number of computer experiments on instances based on the OR-Library generation scheme to illustrate and ascertain the numerical properties of the proposed methods. The results indicate that for larger instances the proposed alternative relaxation and scaling approaches have a much better convergence rate with little to no decrease in solution quality. The results also show that the proposed local-search metaheuristic is a viable alternative to the existing solving methods.

Détail

Keywords: Lagrangian relaxation, scheduling problem, total weighted tardiness, metaheuristics
Mots-clés : relaksacja Lagrange'a, problem harmonogramowania, metaheurystyka

Bibliographie

[1] Ali, S.M., Fathollahi-Fard, A.M., Ahnaf, R. and Wong, K.Y. (2023). A multi-objective closed-loop supply chain under uncertainty: An efficient Lagrangian relaxation reformulation using a neighborhood-based algorithm, Journal of Cleaner Production 423: 138702, DOI: 10.1016/j.jclepro.2023.138702.

[2] Araújo, C.V.D., de Souza, C.C. and Usberti, F.L. (2024). Lagrangian relaxation for maximum service in multicast routing with QoS constraints, International Transactions in Operational Research 31(1): 140-166, DOI: 10.1111/itor.13200.

[3] Beasley, J.E. (1990). OR-Library, http://people.brunel.ac.uk/~mastjjb/jeb/info.html.

[4] Bilge, Ü., Kurtulan, M. and Kıraç, F. (2007). A tabu search algorithm for the single machine total weighted tardiness problem, European Journal of Operational Research 176(3): 1423-1435, DOI: 10.1016/j.ejor.2005.10.030.

[5] Bragin, M.A., Luh, P.B., Yan, J.H., Yu, N. and Stern, G.A. (2015). Convergence of the surrogate Lagrangian relaxation method, Journal of Optimization Theory and Applications 164(1): 173-201, DOI: 10.1007/s10957-014-0561-3.

[6] Butt, A.A. and Collins, R.T. (2013). Multi-target tracking by Lagrangian relaxation to min-cost network flow, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Portland, USA, pp. 1846-1853, DOI: 10.1109/CVPR.2013.241.

[7] Chen, H. and Luh, P.B. (2003). An alternative framework to Lagrangian relaxation approach for job shop scheduling, European Journal of Operational Research 149(3): 499-512, DOI: 10.1109/CDC.1999.832909.

[8] Congram, R.K., Potts, C.N. and van de Velde, S.L. (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem, INFORMS Journal on Computing 14(1): 52-67, DOI: 10.1287/ijoc.14.1.52.7712.

[9] Crauwels, H., Potts, C.N. and Van Wassenhove, L.N. (1998). Local search heuristics for the single machine total weighted tardiness scheduling problem, INFORMS Journal on Computing 10(3): 341-350, DOI: 10.1287/ijoc.10.3.341.

[10] Cui, H. and Luo, X. (2017). An improved Lagrangian relaxation approach to scheduling steelmaking-continuous casting process, Computers & Chemical Engineering 106: 133-146, DOI: 10.1016/j.compchemeng.2017.05.026.

[11] Everett, H. (1963). Generalized Lagrange multiplier method for solving problems of optimum allocation of resources, Operations Research 11(3): 399-417, DOI: 10.1287/opre.11.3.399.

[12] Fisher, M.L. (1976). A dual algorithm for the one-machine scheduling problem, Mathematical Programming 11(1): 229-251, DOI: 10.1007/BF01580393.

[13] Fisher, M.L. (2004). The Lagrangian relaxation method for solving integer programming problems, Management Science 50(12_supp): 1861-1871, DOI: 10.1287/mnsc.1040.0263.

[14] Fu, Y.-M. and Diabat, A. (2015). A Lagrangian relaxation approach for solving the integrated quay crane assignment and scheduling problem, Applied Mathematical Modelling 39(3-4): 1194-1201, DOI: 10.1016/j.apm.2014.07.006.

[15] Gaudioso, M., Gorgone, E., Labbé, M. and Rodríguez-Chía, A.M. (2017). Lagrangian relaxation for SVM feature selection, Computers & Operations Research 87: 137-145, DOI: 10.1016/j.cor.2017.06.001.

[16] Gocgun, Y. and Ghate, A. (2012). Lagrangian relaxation and constraint generation for allocation and advanced scheduling, Computers & Operations Research 39(10): 2323-2336, DOI: 10.1016/j.cor.2011.11.017.

[17] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnoy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5: 287-326, DOI: 10.1016/S0167-5060(08)70356-X.

[18] Hajibabaei, M. and Behnamian, J. (2023). Fuzzy cleaner production in assembly flexible job-shop scheduling with machine breakdown and batch transportation: Lagrangian relaxation, Journal of Combinatorial Optimization 45(5): 112, DOI: 10.1007/s10878-023-01046-1.

[19] Held, M., Wolfe, P. and Crowder, H.P. (1974). Validation of subgradient optimization, Mathematical Programming 6(1): 62-88, DOI: 10.1007/BF01580223.

[20] Huang, D., Wang, Y., Jia, S., Liu, Z. and Wang, S. (2023). A lagrangian relaxation approach for the electric bus charging scheduling optimisation problem, Transportmetrica A: Transport Science 19(2): 2023690, DOI: 10.1080/23249935.2021.2023690.

[21] Idzikowski, R. (2023). LagrangianRelaxation, Code and experimental results, https://github.com/ridzikowski/LagrangianRelaxation.

[22] Koulamas, C. (2010). The single-machine total tardiness scheduling problem: Review and extensions, European Journal of Operational Research 202(1): 1-7, DOI: 10.1016/j.ejor.2009.04.007.

[23] Lawler, E.L. (1977). A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics 1: 331-342, DOI: 10.1016/S0167-5060(08)70742-8.

[24] Lenstra, J.K., Kan, A.R. and Brucker, P. (1977). Complexity of machine scheduling problems, Annals of Discrete Mathematics 1: 343-362, DOI: 10.1016/S0167-5060(08)70743-X.

[25] Liu, X., Wang, W., Chen, X., Sterna, M. and Blazewicz, J. (2023). Exact approaches to late work scheduling on unrelated machines, International Journal of Applied Mathematics and Computer Science 33(2): 285-295, DOI: 10.34768/amcs-2023-0021.

[26] Matsuo, H., Juck Suh, C. and Sullivan, R.S. (1989). A controlled search simulated annealing method for the single machine weighted tardiness problem, Annals of Operations Research 21(1): 85-108, DOI: 10.1007/BF02022094.

[27] Nishi, T., Hiranaka, Y. and Inuiguchi, M. (2010). Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness, Computers & Operations Research 37(1): 189-198, DOI: 10.1016/j.cor.2009.04.008.

[28] Nowak, M.P. and Römisch, W. (2000). Stochastic Lagrangian relaxation applied to power scheduling in a hydro-thermal system under uncertainty, Annals of Operations Research 100(1-4): 251-272, DOI: 10.1023/A:1019248506301.

[29] Potts, C.N. and Van Wassenhove, L.N. (1985). A branch and bound algorithm for the total weighted tardiness problem, Operations Research 33(2): 363-377, DOI: 10.1287/opre.33.2.363.

[30] Potts, C. and Van Wassenhove, L.N. (1991). Single machine tardiness sequencing heuristics, IIE Transactions 23(4): 346-354, DOI: 10.1080/07408179108963868.

[31] Simanchev, R.Y. and Urazova, I. (2023). Integer models for the total weighted tardiness problem on a single machine, International Conference on Mathematical Optimization Theory and Operations Research, Ekaterinburg, Russia, pp. 176-187, DOI: 10.1007/978-3-031-43257-6_14.

[32] Song, M., Cheng, L. and Lu, B. (2024). Solving the multi-compartment vehicle routing problem by an augmented Lagrangian relaxation method, Expert Systems with Applications A 237: 121511, DOI: 10.1016/j.eswa.2023.121511.

[33] Song, M., Lu, B., Cheng, L. and Sun, C. (2023). Lagrangian relaxation-based decomposition approaches for the capacitated arc routing problem in the state-space-time network, Transportation Letters 15(10): 1317-1336, DOI: 10.1080/19427867.2022.2148368.

[34] Speckenmeyer, P., Hilmer, C., Rauchecker, G. and Schryen, G. (2023). Parallel branch-and-price algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times, SSRN: 4537436, (preprint).

[35] Zakharova, Y. (2023). Hybrid evolutionary algorithm with optimized operators for total weighted tardiness problem, International Conference on Mathematical Optimization Theory and Operations Research, Ekaterinburg, Russia, pp. 224-238, DOI: 10.1007/978-3-031-35305-5_15.

[36] Zhang, C., Gao, Y., Yang, L., Gao, Z. and Qi, J. (2020). Joint optimization of train scheduling and maintenance planning in a railway network: A heuristic algorithm using Lagrangian relaxation, Transportation Research B: Methodological 134: 64-92, DOI: 10.1016/j.trb.2020.02.008.

[37] Zhao, Q. and Yuan, J. (2023). Single-machine primary-secondary scheduling with total tardiness being the primary criterion, Journal of Scheduling 27(3): 1-10, DOI: 10.1007/s10951-023-00793-7.

[38] Zhou, Y. and Lee, G.M. (2017). A Lagrangian relaxation-based solution method for a green vehicle routing problem to minimize greenhouse gas emissions, Sustainability 9(5): 776, DOI: 10.3390/su9050776.