рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2026. Vol 56

Solving the Problem of Minimizing the Maximum Lateness with a Convex Resource Constraint

Author(s)

Yulia V. Zakharova 1,2 , Dmitry D. Gorodetsky 2, Aleksey O. Zakharov 1

1 Omsk Branch of the Sobolev Institute of Mathematics SB RAS, Omsk, Russian Federation 

2 Dostoevsky Omsk State University, Omsk, Russian Federation

Abstract
This paper addresses a scheduling problem where each job is characterized by its processing requirements and machine needs. The optimization criterion minimizes maximum lateness relative to given job deadlines, with job durations following a convex resource consumption function under limited total resource availability. We analyze the problem’s computational complexity, develop approximation methods for special cases, and construct mathematical programming models that yield new schedule properties.
About the Authors

Yulia V. Zakharova, Cand. Sci. (Phys.-Math.), Omsk Branch of the Sobolev Institute of Mathematics SB RAS, Omsk, 644099, Russian Federation, yzakharova@ofim.oscsbras.ru

Dmitry D. Gorodecky, Dostoevsky Omsk State University, Omsk, 644077, Russian Federation, gorodeckiydimchik@gmail.com

Aleksey O. Zakharov, Cand. Sci. (Phys.-Math.), Omsk Branch of the Sobolev Institute of Mathematics SB RAS, Omsk, 644099, Russian Federation, azakharov@ofim.oscsbras.ru

For citation
Zakharova Y. V., Gorodetsky D. D., Zakharov A. O. Solving the Problem of Minimizing the Maximum Lateness with a Convex Resource Constraint. The Bulletin of Irkutsk State University. Series Mathematics, 2026, vol. 56, pp. 3–18. (in Russian) https://doi.org/10.26516/1997-7670.2026.56.3
Keywords
schedule, algorithm, approximation, resource
UDC
519.8
MSC
90C27, 90C59, 68W25
DOI
https://doi.org/10.26516/1997-7670.2026.56.3
References
  1. Zakharova Y.V., Evtina A.O. Constructive algorithms for the scheduling problem on two processors with the maximum time offset criterion taking into account parallelization and energy consumption. Prikl. Diskr. Mat., 2025, no. 67, pp. 118–128. https://doi.org/10.17223/20710410/67/7 (in Russian)
  2. Bampis E., Letsios D., Milis I., Zois G. Speed scaling for maximum lateness. International Computing and Combinatorics Conference. Berlin, Heidelberg, Springer, 2012, pp. 25–36. https://doi.org/10.1007/978-3-642-32241-9_3
  3. Beasley J.E. OR-library: weighted tardiness. Available at: https://people.brunel.ac.uk/ mastjjb/jeb/orlib/wtinfo.html
  4. Caponio A., Neri F., Tirronen V. Super-fit control adaptation in memetic differential evolution frameworks. Soft Computing, 2009, vol. 13, pp. 811–831.
  5. Garey M.R., Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, Calif., W. H. Freeman and Co., 1979, 338 p.
  6. Gerards M.E.T., Hurink J.L., Holzenspies P.K.F. A survey of offline algorithms for energy minimization under deadline constraints. J. Scheduling, 2016, vol. 19, pp. 3–19. https://doi.org/10.1007/s10951-015-0463-8
  7. Gr¨otschel M., Lov´asz L., Schrijver A. Geometric Algorithms and Combinatorial Optimizations, 2nd correct. ed. Berlin, Springer-Verlag, 1993, 362 p.
  8. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT press, 1992. 211 p.
  9. Kononov A., Kovalenko Y. On speed scaling scheduling of parallel jobs with preemption. DOOR-2016, LNCS, 2016, vol. 9869, pp. 309–321. https://doi.org/10.1007/978-3-319-44914-2_25
  10. Kononov A., Kovalenko Y. Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems. Siberian Electronic Mathematical Reports, 2019, vol. 16, pp. 249-257. https://doi.org/10.33048/semi.2019.16.016
  11. Kononov A., Zakharova Y. Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion. J. Glob. Optim., 2022, vol. 83, pp. 539–564. https://doi.org/10.1007/s10898-021-01115-x
  12. Neumann A., Hajji A., Rekik M., Pellerin R. Genetic algorithms for planning and scheduling engineer-to-order production: A systematic review. International Journal of Production Research, 2024, vol. 62, no. 8, pp. 2888–2917.
  13. Shabtay D., Kaspi M. Parallel machine scheduling with a convex resource consumption function. European Journal of Operational Research, 2006, vol. 173, no. 1, pp. 92–107. https://doi.org/10.1016/j.ejor.2004.12.008
  14. Shabtay D., Kaspi M. Minimizing the makespan in open–shop scheduling problems with a convex resource consumption function. Naval Research Logistics, 2006, vol. 53, no. 3, pp. 204–216. https://doi.org/10.1002/nav.20133
  15. Zakharova Y.V. Approximation algorithms for Open Shop variations subject to energy consumption. Proceedings of the Steklov Institute of Mathematics, 2024, vol. 327, pp. S286–S301. https://doi.org/10.1134/S0081543824070216

Full text (russian)