Проводится теоретический и экспериментальный анализ вычислительной сложности одной актуальной задачи теории расписаний, возникающей в компьютерных системах и приложениях. Особенностью постановки является возможность распараллеливания операций и учёт ресурсных ограничений, влияющих на длительности операций. Критерием выступает минимизация максимального временного смещения. Исследуется вопрос труднорешаемости задачи и предлагаются алгоритмы с гарантированными оценками точности. Результаты экспериментальных исследований показывают перспективность предложенных алгоритмов.
Скачать электронную версию публикации
Загружен, раз: 15
- Title Конструктивные алгоритмы для задачи составления расписаний на двух процессорах с критерием максимального временного смещения при учете распараллеливания и расхода энергии
- Headline Конструктивные алгоритмы для задачи составления расписаний на двух процессорах с критерием максимального временного смещения при учете распараллеливания и расхода энергии
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 67
- Date:
- DOI 10.17223/20710410/67/7
Ключевые слова
расписание, ресурс, алгоритм, NP-трудностьАвторы
Ссылки
Drozdowski M. Scheduling for Parallel Processing. Dordrecht: Springer, 2009. 386 p.
Сервах В. В. Эффективно-разрешимый случай задачи календарного планирования с возобновимыми ресурсами // Дискретн. анализ и исслед. опер. 2000. Оер. 2. Т. 7. №1. С. 75-82.
Коваленко Ю. В. О задаче календарного планирования с возобновимым ресурсом // Автомат. и телемех. 2012. №6. C. 140-153.
Goncharov E. N. An improved genetic algorithm for the resource-constrained project scheduling problem // N. Olenev, Yu. Evtushenko, M. Jacimovic, et al. (eds). Advances in Optimization and Applications. Springer, Cham, 2022. P.35-47.
Zhuravlev S., Blagodurov S., and Fedorova A. Addressing shared resource contention in multicore processors via scheduling // Comput. Archit. News. 2010. V. 38. No. 1. P. 129-142.
Еремеев А. В., Сахно М. Ю. Построение расписания для многоядерного процессора с учетом взаимного влияния работ // Выч. мет. программирование. 2023. Т. 24. №1. С. 115-126.
Kononov A. and Kovalenko Y. On speed scaling scheduling of parallel jobs with preemption // LNCS. 2016. V.9869. P. 309-321.
Kononov A. and Zakharova Y. Speed scaling scheduling of multiprocessor jobs with energy constraint and total completion time criterion // Intern. J. Artif.Intell. 2023. V. 21. No. 2. P. 109-129.
Gerards M. E. T., Hurink J. L., and Holzenspies P. K. F. A survey of offline algorithms for energy minimization under deadline constraints // J. Scheduling. 2016. V. 19. P. 3-19.
Shabtay D. and Kaspi M. Parallel machine scheduling with a convex resource consumption function // Europ. J. Oper. Res. 2006. V. 173. No. 1. P.92-107.
https://www2.informatik.uni-osnabrueck.de/knust/class/- Complexity Results for Scheduling Problems. 2024.
Lee C.-Y. and Cai X. Scheduling one and two-processor tasks on two parallel processors // IIE Trans. 1999. V.31. P.445-455.
Lenstra J.K., Rinnooy Kan A.H.G., and Brucker P.Complexity of machine scheduling problems // Ann. Discrete Math. 1977. V. 1. P.343-362.
Grotschel M., Lovasz L., and Schrijver A. Geometric Algorithms and Combinatorial Optimizations. Heidelberg: Springer, 2009. 332 p.
Garey M. and Johnson D.Computers and Intractability. A Guide to the Theory of NP-completeness. N.Y.: W. H. Freeman and Company, 1979. 338 p.
Конструктивные алгоритмы для задачи составления расписаний на двух процессорах с критерием максимального временного смещения при учете распараллеливания и расхода энергии | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/7
Скачать полнотекстовую версию
Загружен, раз: 194