рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2026. Том 56

Решение задачи минимизации максимального временного смещения при наличии выпуклого ограничения по ресурсу

Автор(ы)

Ю. В. Захарова1,2, Д. Д. Городецкий2 , А. О. Захаров1

1 Омский филиал Института математики им. С. Л. Соболева СО РАН, Омск, Российская Федерация

2 Омский государственный университет им. Ф. М. Достоевского, Омск, Российская Федерация

Аннотация
Требуется составить расписание выполнения работ на машинах. Каждая работа характеризуется объемом и числом используемых машин. Минимизируется максимальное временное смещение от заданных директивных сроков работ. Длительности работ зависят от потребления ресурса через выпуклую функцию. Общий доступный объем ресурса ограничен. Для задачи исследуется ее алгоритмическая сложность и предлагаются методы приближенного решения в частных случаях. Строятся модели математического программирования, позволяющие получить новые свойства расписаний.
Об авторах

Захаров Алексей Олегович, канд. физ.-мат. наук, Омский филиал Института математики им. С. Л. Соболева СО РАН, Омск, 644099, Российская Федерация, azakharov@ofim.oscsbras.ru

Захарова Юлия Викторовна, канд. физ.-мат. наук, Омский филиал Института математики им. С. Л. Соболева СО РАН, Омск, 644099, Российская Федерация, yzakharova@ofim.oscsbras.ru

Городецкий Дмитрий Дмитриевич, Омский государственный университет им. Ф. М. Достоевского, Омск, 644077, Российская Федерация, gorodeckiydimchik@gmail.com

Ссылка для цитирования
Захарова Ю. В., Городецкий Д. Д., Захаров А. О. Решение задачи минимизации максимального временного смещения при наличии выпуклого ограничения по ресурсу // Известия Иркутского государственного университета. Серия Математика. 2026. Т. 56. C. 3–18. https://doi.org/10.26516/1997-7670.2026.56.3
Ключевые слова
расписание, алгоритм, аппроксимация, ресурс
УДК
519.8
MSC
90C27, 90C59, 68W25
DOI
https://doi.org/10.26516/1997-7670.2026.56.3
Литература
  1. Захарова Ю. В., Евтина А. О. Конструктивные алгоритмы для задачи составления расписаний на двух процессорах с критерием максимального временного смещения при учете распараллеливания и расхода энергии // Прикладная дискретная математика. 2025. № 67. С. 118–128.
  2. Speed scaling for maximum lateness / E. Bampis, D. Letsios, I. Milis, G. Zois // International Computing and Combinatorics Conference. Berlin, Heidelberg : Springer, 2012. P. 25–36. https://doi.org/10.1007/978-3-642-32241-9_3
  3. Beasley J. E. OR-library: Weighted tardiness. URL: 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. P. 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. P. 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 corrected 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. P. 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. P. 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. P. 539–564. https://doi.org/10.1007/s10898-021-01115-x
  12. Genetic algorithms for planning and scheduling engineer-to-order production: A systematic review / A. Neumann, A. Hajji, M. Rekik, R. Pellerin // International Journal of Production Research. 2024. Vol. 62, N 8. P. 2888–2917.
  13. Shabtay D., Kaspi M. Parallel machine scheduling with a convex resource consumption function // European Journal of Operational Research. 2006. Vol. 173, N 1. P. 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, N 3. P. 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. P. S286–S301. https://doi.org/10.1134/S0081543824070216

Полная версия (русская)