Total Tardiness Minimization in a Single-Machine with Periodical Resource Constraints

Main Article Content

Bruno Prata
Levi Ribeiro de Abreu
Marcelo Seido Nagano


Production Sequencing, Combinatorial Optimization, Matheuristics, Resource Consumption


In this paper we introduce a variant of the single machine considering resource restriction per period. The objective function to be minimized is the total tardiness.  We proposed an integer linear programming modeling based on a bin packing formulation. In view of the NP-hardness of the introduced variant, heuristic algorithms are required to find high-quality solutions within an admissible computation times. In this sense, we present a new hybrid matheuristic called Relax-and-Fix with Variable Fixing Search (RFVFS).  This innovative solution approach combines the relax-and-fix algorithm and a strategy for the fixation of decision variables based on the concept of the variable neighborhood search metaheuristic. As statistical indicators to evaluate the solution procedures under comparison, we employ the Average Relative Deviation Index (ARDI) and the Success Rate (SR). We performed extensive computational experimentation with a testbed composed by 450 proposed test problems. Considering the results for the number of jobs, the RFVFS returned ARDI and SR values of 35.6% and 41.3%, respectively. Our proposal outperformed the best solution approach available for a closely-related problem with statistical significance.


Download data is not yet available.


[1] M. Afzalirad and J. Rezaeian, “Resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times, precedence constraints and machine eligibility restrictions,” Computers & Industrial Engineering, vol. 98, pp. 40 – 52, 2016.
[2] M. Afzalirad and M. Shafipour, “Design of an efficient genetic algorithm for a resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions,” Journal of Intelligent Manufacturing, vol. 29, no. 2, pp. 423–437, 2018.
[3] M. Akbar and T. Irohara, “Scheduling for sustainable manufacturing: A review,” Journal of cleaner production, vol. 205, pp. 866–883, 2018.
[4] M. P. Antonioli, C. D. Rodrigues, and B. A. Prata, “Minimizing total tardiness for the order scheduling problem with sequence-dependent setup times using hybrid metaheuristics,” International Journal of Industrial Engineering Computations, vol. 13, 2022.
[5] F. Della Croce and F. Salassa, “A variable neighborhood search based metaheuristic for nurse rostering problems,” Annals of Operations Re-search, vol. 218, no. 1, pp. 185–199, 2014.
[6] F. Della Croce, V. Narayan, and R. Tadei, “The two-machine total completion time flow shop problem,” European Journal of Operational Research, vol. 90, no. 2, pp. 227–237, 1996.
[7] F. Della Croce, F. Salassa, and V. T’kindt, “A hybrid heuristic approach for single machine scheduling with release times,” Computers & Operations Research, vol. 45, pp. 7–11, 2014.
[8] E. B. Edis and I. Ozkarahan, “Solution approaches for a real-life resource-constrained parallel machine scheduling problem,” The International Journal of Advanced Manufacturing Technology, vol. 58, no. 9, pp. 1141–1153, 2012.
[9] E. B. Edis, C. Oguz, and I. Ozkarahan, “Parallel machine scheduling with additional resources: Notation, classification, models and solution methods,” European Journal of Operational Research, vol. 230, no. 3, pp. 449 – 463, 2013.
[10] L. Fanjul-Peyro, F. Perea, and R. Ruiz, “Models and metaheuristics for the unrelated parallel machine scheduling problem with additional resources,” European Journal of Operational Research, vol. 260, no. 2, pp. 482 – 493, 2017.
[11] V. Fernandez-Viagas and J. M. Framinan, “Neh-based heuristics for the permutation flow shop scheduling problem to minimize total tardiness,” Computers & Operations Research, vol. 60, pp. 27–36, 2015.
[12] J. M. Framinan and P. Perez-Gonzalez, “Order scheduling with tardiness objective: Improved approximate solutions,” European Journal of Operational Research, vol. 266, no. 3, pp. 840–850, 2018.
[13] O. Herr and A. Goel, “Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints,” European Journal of Operational Research, vol. 248, no. 1, pp. 123–135, 2016.
[14] M. Ji, J.-Y. Wang, and W.-C. Lee, “Minimizing resource consumption on uniform parallel machines with a bound on makespan,” Computers & Operations Research, vol. 40, no. 12, pp. 2970 – 2974, 2013.
[15] S. Karhi and D. Shabtay, “Single machine scheduling to minimise resource consumption cost with a bound on scheduling plus due date assignment penalties,” International Journal of Production Research, vol. 56, no. 9, pp. 3080–3096, 2018.
[16] A. B. Keha, K. Khowala, and J. W. Fowler, “Mixed integer programming formulations for single machine scheduling problems,” Computers & Industrial Engineering, vol. 56, no. 1, pp. 357–367, 2009.
[17] Y. Kochetov and A. Kondakov, “Vns metaheuristic for a bin packing problem with a color constraint,” Electronic Notes in Discrete Mathematics, vol. 58, pp. 39–46, 2017.
[18] S.-W. Lin and K.-C. Ying, “Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics,” Omega, vol. 64, pp. 115–125, 2016.
[19] M. Lubin and I. Dunning, “Computing in operations research using julia,” INFORMS Journal on Computing, vol. 27, no. 2, pp. 238–248, 2015.
[20] S. Martello, “Knapsack problems: algorithms and computer implementations,” Wiley-Interscience series in discrete mathematics and optimization, 1990.
[21] N. Mladenovic and P. Hansen, “Variable neighborhood search,” Computers & operations research, vol. 24, no. 11, pp. 1097–1100, 1997.
[22] J. C. Pinheiro and J. E. C. Arroyo, “Effective IG heuristics for a single-machine scheduling problem with family setups and resource constraints,” Annals of Mathematics and Artificial Intelligence, vol. 88, no. 1-3, pp. 169–185, 2020.
[23] A. R. Pitombeira-Neto and B. d. A. Prata, “A matheuristic algorithm for the one-dimensional cutting stock and scheduling problem with heterogeneous orders,” TOP, Sep 2019.
[24] B. A. Prata, A. R. Pitombeira-Neto, and C. J. M. Sales, “An integer linear programming model for the multiperiod production planning of precast concrete beams,” Journal of Construction Engineering and Management, vol. 141, no. 10, p. 04015029, 2015.
[25] B. A. Prata, L. R. de Abreu, and J. Y. F. Lima, “Heuristic methods for the single-machine scheduling problem with periodical resource constraints,” TOP, pp. 1–23, 2020.
[26] B. A. Prata, C. D. Rodrigues, and J. M. Framinan, “Customer order scheduling problem to minimize makespan with sequence-dependent setup times,” Computers & Industrial Engineering, vol. 151, p. 106962, 2021.
[27] E. Rahimian, K. Akartunalı, and J. Levine, “A hybrid integer programming and variable neighbourhood search algorithm to solve nurse rostering problems,” European Journal of Operational Research, vol. 258, no. 2, pp. 411–423, 2017.
[28] G. Scheithauer, Introduction to Cutting and Packing Optimization: Problems, Modeling Approaches, Solution Methods. Springer, 2017, vol. 263.
[29] D. Shabtay, “Single-machine scheduling with machine unavailability periods and resource dependent processing times,” European Journal of Operational Research, 2021.
[30] J. P. Sousa and L. A. Wolsey, “A time-indexed formulation of non-preemptive single machine scheduling problems,” Mathematical programming, vol. 54, no. 1-3, pp. 353–367, 1992.
[31] J. A. Ventura and D. Kim, “Parallel machine scheduling with earliness–tardiness penalties and additional resource constraints,” Computers & Operations Research, vol. 30, no. 13, pp. 1945 – 1958, 2003.
[32] F. Villa, E. Vallada, and L. Fanjul-Peyro, “Heuristic algorithms for the unrelated parallel machine scheduling problem with one scarce additional resource,” Expert Systems with Applications, vol. 93, pp. 28 – 38, 2018.
[33] J.-B. Wang and M.-Z. Wang, “Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time,” Computers & Operations Research, vol. 39, no. 3, pp. 492 – 497, 2012.
[34] X.-R. Wang and J.-J. Wang, “Single-machine scheduling with convex resource-dependent processing times and deteriorating jobs,” Applied Mathematical Modelling, vol. 37, no. 4, pp. 2388 – 2393, 2013.
[35] L. Wu and C.-D. Cheng, “On single machine scheduling with resource constraint,” Journal of Combinatorial Optimization, vol. 31, no. 2, pp. 491–505, 2016.
[36] W.-C. Yeh, M.-C. Chuang, and W.-C. Lee, “Uniform parallel machine scheduling with resource consumption constraint,” Applied Mathematical Modelling, vol. 39, no. 8, pp. 2131 – 2138, 2015.
[37] Z. Zhu, F. Chu, L. Sun, and M. Liu, “Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity,” Applied Mathematical Modelling, vol. 37, no. 7, pp. 5371 – 5380, 2013.