Математические модели и списочные алгоритмы для построения расписаний в многопроцессорных системах с ресурсными ограничениями тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Сахно Мария Юрьевна

• Сахно Мария Юрьевна
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Сахно Мария Юрьевна

Введение

1 Задача составления расписаний выполнения работ в компьютерных системах с учетом ресурсов

возобновимого типа

1.1 Обзор известных результатов

1.2 Задача построения расписания для многоядерного процессора

с учетом взаимного влияния работ

1.2.1 Постановка задачи

1.2.2 Вычислительная сложность

1.2.3 Математическая модель

1.3 Задача построения расписания для многоядерного процессора

с учетом потребления шины данных

1.3.1 Постановка задачи

1.3.2 Вычислительная сложность

1.3.3 Жадный алгоритм и алгоритм списочного типа

1.4 Задача назначения работ на машины с NUMA-архитектурой с учетом возобновимых ресурсов

1.4.1 Постановка задачи

1.4.2 Вычислительная сложность и математическая модель

1.4.3 Алгоритм списочного типа

1.5 Вычислительный эксперимент

2 Задача составления расписания выполнения работ на процессорах с учетом расхода энергии

2.1 Обзор известных результатов

2.2 Постановка задачи

2.2.1 Задача составления расписания выполнения

распараллеливаемых работ на процессорах с

ограничением на расход энергии

Стр.

2.2.2 Задача построения энергоэффективных расписаний

выполнения работ на процессорах

2.3 Задача составления расписания выполнения распараллеливаемых работ на процессорах с ограничением на расход энергии

2.3.1 Вычислительная сложность

2.3.2 Математическая модель

2.3.3 Алгоритм списочного типа и локальные улучшения

2.3.4 Метод генерации данных

2.3.5 Вычислительный эксперимент

2.4 Задача построения энергоэффективных расписаний выполнения работ на процессорах

2.4.1 Вычислительная сложность

2.4.2 Математическая модель

2.4.3 Алгоритм списочного типа

2.4.4 Метод генерации данных

2.4.5 Вычислительный эксперимент

3 Адаптивный генетический алгоритм с

оптимизированными операторами

3.1 Обзор известных результатов

3.2 Кодировка решений

3.3 Рандомизированные операторы

3.4 Оптимальная рекомбинация

3.5 Адаптивная схема

3.6 Сходимость генетического алгоритма

3.7 Вычислительный эксперимент

3.7.1 Задачи построения расписания для многоядерного процессора с учетом взаимного влияния работ

3.7.2 Задача составления расписания выполнения распараллеливаемых работ на процессорах с ограничением на расход энергии

3.7.3 Задача построения энергоэффективных расписаний выполнения работ на процессорах

Стр.

4 Комплекс программ и его применение для решения

практических задач

4.1 Применение разработанного математического аппарата для решения практических задач

4.1.1 Применение разработанного математического аппарата для решения задачи размещения виртуальных машин

по серверам

4.1.2 Применение разработанного математического аппарата для решения задачи планирования выполнения работ

на процессорах Intel

4.2 Структура и технические особенности программного комплекса

4.2.1 Библиотека классов решателя Heuristic

4.2.2 Библиотека для запуска моделей математического программирования Solver

4.2.3 Комплекс программ для реализации расписаний для задачи планирования работ на ядрах процессора с

учетом их взаимного влияния в реальном эксперименте

Заключение

Список литературы

Приложение А Доказательство NP-трудности задачи

Р 2| sizej ,energy\J2 Cj

Приложение Б Акт о внедрении

Приложение В Свидетельства о государственной

регистрации программы для ЭВМ

Введение диссертации (часть автореферата) на тему «Математические модели и списочные алгоритмы для построения расписаний в многопроцессорных системах с ресурсными ограничениями»

ВВЕДЕНИЕ

В данной работе исследуются математические модели, связанные с задачами составления расписаний, возникающими в многопроцессорных компьютерных системах, например, при разработке программы для выполнения на многоядерном процессоре. Многопроцессорные системы характеризуются такими свойствами, как наличие общего ресурса и возможность распараллеливания вычислений. Математические модели для составления расписаний выполнения подпрограмм (работ) на процессорах или ядрах процессора должны учитывать оба эти свойства. Задачи оптимизации, возникающие в рамках этих моделей, актуальны для производителей процессоров и компаний, разрабатывающих многопоточное программное обеспечение, поскольку их решение может повысить скорость работы программного обеспечения.

Работы могут влиять друг на друга при совместном выполнении из-за наличия общего ресурса. Например, скорость выполнения работы может меняться в зависимости от загрузки других ядер процессора в случае, когда разным работам необходимо передавать разный объем данных по шине данных. Может возникнуть конкуренция за шину данных и выполнение каждой из работ в этом случае может занять больше времени, чем в случае одно-поточного выполнения. Необходимо составить расписание выполнения работ на ядрах процессора, учитывая их взаимное влияние друг на друга. Длительности работ также зависят от скорости, с которыми они выполняются, что влияет на общее потребление такого ресурса, как энергия: чем с большей скоростью выполняется работа, тем больше энергии на неё затрачивается, но тем меньше её длительность. В этом случае необходимо распределить энергию между работами таким образом, чтобы минимизировать её расход или уложиться в заданные границы.

Характерным свойством многопроцессорных систем является распараллеливание. Это означает, что каждая работа может выполняться на двух и более процессорах одновременно (также можно рассматривать ядра). Существует несколько основных типов, определяющих степень распараллеливания работ: задано необходимое количество процессоров (англ. rigid) или задана верхняя граница на число используемых процессоров, при этом фактическое количество определяется перед началом выполнения работы (англ. moldable)

или может изменяться в процессе выполнения (англ. malleable) [48]. Это также важно учитывать при составлении расписания выполнения работ.

Многопроцессорные компьютерные системы часто реализуются с использованием NUMA-архитектуры (англ. Non-Uniform Memory Access) [81]. В таких системах процессорные ядра и модули оперативной памяти объединены в NUMA-узлы, внутри которых доступ к памяти осуществляется быстрее, чем к памяти других узлов. При этом задачи и процессы могут быть размещены как в пределах одного NUMA-узла, так и с использованием ресурсов нескольких узлов одновременно. Эта особенность также важна при размещении виртуальных машин на серверах, где ресурсы (ядра процессора и объём памяти) распределены между NUMA-узлами. Для эффективного использования аппаратных ресурсов и минимизации задержек критично учитывать NUMA-архитектуру.

В литературе существует ряд подходов к планированию назначения работ на ядра процессора с учетом переменной длительности их выполнения. Как правило, такие задачи решаются с помощью быстрых эвристических алгоритмов, которые работают в онлайн-режиме, т.е. работы поступают последовательно и в каждый момент времени рассматривается только ограниченное количество работ. Эвристические алгоритмы для планирования работ, предложенные в [87], [128] и некоторых других статьях, используют стратегию, которая старается размещать работы на ядра процессора комплементарным образом, чтобы работы с наиболее различными потребностями в использовании ресурсов выполнялись одновременно (в [87], [128] под такими ресурсами подразумевается пропускная способность шины данных и кэш на разных уровнях).

Задача размещения виртуальных машин по серверам представляет собой обобщение темпоральной задачи упаковки в контейнеры, в которой каждый предмет занимает ресурсы в течение заданного временного интервала [23]. Для её решения используются как точные методы, например, основанные на ветвлении [45], так и приближённые подходы: жадные эвристические алгоритмы [46], метод генерации столбцов [102], генетический алгоритм [104] и другие.

Для задач, где ресурсом выступает энергия, известно много теоретических исследований. В [99] исследуется задача минимизации среднего времени выполнения работ в однопроцессорной системе при фиксированном коли-

честве энергии и с заданным временем поступления каждой работы. Для выполнения работ идентичного объема предложен алгоритм с полиномиальным временем. В [35] этот подход применяется к задаче с несколькими процессорами и работами произвольного объема. В [120] исследуется задача с критерием минимизации потребляемой энергии с одним процессором и с возможностью прерывать выполнение работ. Предложен точный алгоритм YDS, оригинальная вычислительная сложность которого - 0(п3), где п - это количество работ. Если же рассмотреть задачу с несколькими процессорами и распараллеливаемыми работами, то такая задача становится NP-трудной даже если прерывания допустимы [71]. В [73; 74] был проведен анализ вычислительной сложности и предложены двухэтапные конструктивные алгоритмы для построения расписаний для произвольного числа процессоров с учетом распараллеливаемых работ и наличием энергии.

Для задач составления расписаний, возникающих в многопроцессорных компьютерных системах, является актуальной разработка метаэвристик, среди которых есть класс эволюционных алгоритмов, хорошо зарекомендовавших себя при решении задач составления расписаний с ресурсными ограничениями [111]. Генетический алгоритм является эволюционным эвристическим алгоритмом, который имитирует процесс естественной эволюции [103]. Чтобы поддерживать достаточный уровень разнообразия популяции применяют, например, механизм перезапуска алгоритма или более интенсивную мутацию [47]. Для осуществления направленного поиска хорошо себя зарекомендовали оптимизированные операторы скрещивания, которые строят лучшего потомка, удовлетворяющего тем или иным свойствам [13]. Значения параметров алгоритма выбираются на этапе препроцессинга или адаптируются в процессе эволюции [49]. Адаптивное управление вызовом операторов использует обратную связь из истории поиска для определения направления дальнейшего поиска. Существуют самоадаптирующиеся (англ. self-adaptive) варианты настройки параметров (см., например, [24]). В данной схеме настраиваемые параметры включены в кодировку особей и также изменяются в процессе эволюции.

Целью данной работы является выявление свойств математических моделей и создание вычислительных методов и комплексов программ, ориентированных на оптимизацию составления расписаний в многопроцессорных

компьютерных системах с учетом ресурсных ограничений, и повышение эффективности решения практических задач.

Для достижения поставленной цели необходимо было решить следующие задачи:

1. Анализ комбинаторных свойств рассматриваемых задач составления расписаний в рамках моделей частичного целочисленного программирования.

2. Исследование вычислительной сложности задач и разработка конструктивных алгоритмов списочного типа, учитывающих специфику задач и позволяющих быстро находить допустимые решения.

3. Разработка и анализ адаптивного эволюционного алгоритма для решения рассматриваемых задач составления расписаний с учетом ограничения на потребление общего ресурса и свойства распараллеливания.

4. Создание комплекса программ, ориентированных на решение поставленных задач. Проведение вычислительных экспериментов.

Научная новизна:

1. Получены новые свойства допустимых решений рассматриваемых задач на основе исследования оригинальных моделей частично целочисленного программирования, использующих концепцию точек событий с непрерывным представлением времени.

2. Доказана КР-трудность задачи составления расписаний с учетом пропускной способности шины данных и задачи составления расписаний при возможности распараллеливания операций с ограничением на расход энергии. Выявлены комбинаторные свойства задач, позволившие сократить трудоемкость предлагаемых алгоритмов для их решения.

3. Разработаны конструктивные алгоритмы списочного типа для решения рассматриваемых задач составления расписаний в компьютерных системах с учетом ресурсов и свойства распараллеливания. Предложенные алгоритмы имеют статистически значимое преимущество перед известными аналогами.

4. Разработан адаптивный эволюционный алгоритм с оптимизированными операторами для составления расписаний в компьютерных системах с учетом ограничения на потребление общего ресурса

и свойства распараллеливания. Данный алгоритм также может использоваться и для других задач составления расписаний на перестановках.

Теоретическая значимость:

1. Доказана КР-трудность задачи составления расписаний на многоядерных процессорах с учетом пропускной способности шины данных.

2. Доказана КР-трудность задачи составления расписаний в многопроцессорных компьютерных системах с учетом расхода энергии и свойства распараллеливания работ.

3. Доказана сходимость предложенного адаптивного эволюционного алгоритма к оптимуму для решения рассматриваемых задач.

4. Выявлены комбинаторные и оптимизационные свойства математических моделей рассматриваемых задач.

Практическая значимость Разработанные конструктивные алгоритмы и адаптивный эволюционный алгоритм для рассматриваемых задач протестированы на сериях тестовых примеров, аналогичных возникающим на практике. Результаты экспериментов показали конкурентное преимущество по сравнению с алгоритмическими пакетами в составе известных решателей (СигоЫ, СРЬЕХ) и онлайн-планировщиком опеТББ. Результаты диссертации могут быть использованы для улучшения планировщиков работы приложений и производителей процессоров, а также для повышения эффективности планирования работ для серверов облачных ресурсов.

Объект исследования - расписания выполнения работ на многоядерных процессорах.

Предметом исследования являются математические модели, методы и комплексы программ составления расписаний выполнения работ на многоядерных процессорах.

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

Основные положения, выносимые на защиту:

1. Выявлены сложностные и комбинаторные свойства конфигураций работ, позволившие разработать конструктивные алгоритмы списочного типа и адаптивный эволюционный алгоритм для составления расписаний выполнения работ с учетом ограничения на потребление общего ресурса и свойства распараллеливания.

2. Разработан эффективный конструктивный алгоритм построения приближенного решения с проблемно-ориентированной стратегией жадного типа назначения работ на ядра процессора, позволяющий учитывать пропускную способность шины данных при планировании выполнения работ в многопоточных системах.

3. Предложен эффективный метод локальных улучшений структурных компонент решений для повышения качества расписаний с возможностью распараллеливания работ и ограничением на расход энергии.

4. Создан комплекс программ, реализующий предложенные математические модели, конструктивные алгоритмы и метаэвристики для составления расписаний в компьютерных системах с учетом ограничения на потребление общего ресурса и свойства распараллеливания, а также модуль запуска планировщика работы приложений.

Соответствие научной специальности. Работа соответствует научной специальности 1.2.2 по п. 3 - Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента; по п. 7 - Качественные или аналитические методы исследования математических моделей; по п. 9 - Постановка и проведение численных экспериментов, статистический анализ их результатов, в том числе с применением современных компьютерных технологий.

Достоверность научных положений, выводов и практических рекомендаций, полученных в диссертации, подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, достаточным количеством численных экспериментов с последующим статистическим анализом, математическими доказательствами теоретических утверждений. Методика проведения численных экспериментов подробно описана, что позволяет воспроизвести полученные результаты.

Апробация работы. Основные результаты диссертации докладывались на следующих конференциях и семинарах:

— международная конференция «Mathematical Optimization Theory and Operations Research» (2021, 2023, 2024, 2025)

— международная научная конференция «Математическое и компьютерное моделирование» (2024, 2025)

— международная конференция «Numerical Computations: Theory and Algorithms» (NUMTA, 2023)

— международная конференция и молодежная школа «Математическое моделирование и суперкомпьютерные технологии» (2024)

— международная конференция «Optimization and Applications» (OPTIMA, 2020, 2022)

— региональная конференция магистрантов, аспирантов и молодых ученых по физике, математике и химии «ФМХ ОмГУ» (2022)

— семинар ОФ ИМ СО РАН «Модели и алгоритмы для задач составления расписаний» (2022, 2023, 2024, 2025)

— семинар ОФ ИМ СО РАН «Математическое моделирование и дискретная оптимизация» (2020, 2022, 2023, 2024, 2025)

Личный вклад. Решение задач диссертации, разработанные алгоритмы и их программная реализация, экспериментальные и теоретические результаты, представленные в диссертации и выносимые на защиту, принадлежат лично автору.

Публикации. Основные результаты диссертации опубликованы в 14 научных работах, две из них изданы в журналах из списка ВАК, одна - в периодических научных журналах, индексируемых Web of Science и Scopus, три - в трудах международных конференций, индексируемых в библиографических зарубежных базах данных публикаций (2020, 2024, 2025). Зарегистрирован один акт о внедрении, получено три свидетельства о государственной регистрации программ для ЭВМ. Конфликт интересов с соавторами отсутствует.

Объем и структура работы. Диссертация состоит из введения, 4 глав, заключения и 3 приложений. Полный объём диссертации составляет 145 страниц, включая 34 рисунка и 38 таблиц. Список литературы содержит 128 наименований.

1 ЗАДАЧА СОСТАВЛЕНИЯ РАСПИСАНИЙ ВЫПОЛНЕНИЯ РАБОТ В КОМПЬЮТЕРНЫХ СИСТЕМАХ С УЧЕТОМ РЕСУРСОВ ВОЗОБНОВИМОГО ТИПА

В данной главе исследуются задачи составления расписаний, возникающие, например, при разработке программы для выполнения на многоядерном процессоре. В этом случае необходимо составить расписание выполнения подпрограмм (работ) на ядрах процессора, учитывая, что они могут влиять друг на друга при совместном выполнении. Таким образом, скорость выполнения работы может меняться в зависимости от загрузки других ядер процессора. Например, разным работам необходимо передавать разный объем данных по шине данных, поэтому в случае одновременного выполнения нескольких работ может возникнуть конкуренция за шину данных и выполнение каждой из работ в этом случае может занять больше времени, чем в случае однопоточного выполнения. Задача планирования работ на многоядерном процессоре актуальна для производителей процессоров и компаний, разрабатывающих многопоточное программное обеспечение, поскольку если учитывать взаимное влияние работ, то можно повысить скорость работы программного обеспечения.

В разделе 1.1 приводится обзор известных научных результатов по задачам составления расписаний выполнения работ с учетом их взаимного влияния за счет общего потребления ресурса. В разделе 1.2 рассматривается задача составления расписаний выполнения работ на ядрах процессора с учетом их взаимного замедления: в 1.2.1 описана постановка задачи, в 1.2.2 исследуется её вычислительная сложность, а в 1.2.3 предложена модель частично целочисленного линейного программирования (ЧЦЛП), использующая концепцию точек событий (см., например, [66]). В разделе 1.3 рассматривается частный случай задачи из раздела 1.2, где в качестве ресурса выступает пропускная способность шины данных: в 1.3.1 описана постановка такой задачи, в 1.3.2 проводится анализ её вычислительной сложности, а в 1.3.3 предложены жадный и списочные алгоритмы для поиска приближенного решения задачи. В разделе 1.4 исследуется задача назначения работ на машины с КИМЛ-архитектурой при наличии нескольких ресурсов возобновимого типа: в 1.4.1 представлена постановка задачи, в 1.4.2 приводят-

ся известные результаты по её вычислительной сложности и математическая модель, а в 1.4.3 предложен алгоритм списочного типа её решения. В разделе 1.5 представлено описание и результаты вычислительного эксперимента.

Основные результаты главы опубликованы в статьях [1; 7; 8; 90] и тезисах трудов конференций [126].

1.1 Обзор известных результатов

В литературе существует ряд подходов к планированию назначения работ на ядра процессора с учетом переменной длительности их выполнения. Как правило, такие задачи решаются с помощью быстрых эвристических алгоритмов, которые работают в онлайн-режиме, т.е. работы поступают последовательно и в каждый момент времени рассматривается только ограниченное количество работ. Эвристические алгоритмы планирования работ, предложенные в [87], [128] и некоторых других статьях, основаны на том принципе, что работы должны размещаться на ядрах процессора комплементарным образом, чтобы работы с наиболее различными потребностями в использовании ресурсов выполнялись одновременно (в [87], [128] под такими ресурсами подразумевается пропускная способность шины данных и кэш на разных уровнях).

Метод планирования работ, предложенный в [17], основан на коэффициентах деградации при совместном выполнении, равных увеличению времени выполнения приложения, когда работы в нем совместно используют кэш, по сравнению с запуском работ в одиночку. В случае двухъядерных процессоров работы могут быть представлены в виде вершин, соединенных ребрами, а веса ребер задаются суммой взаимных деградаций совместного выполнения двух работ. Затем, при некоторых упрощающих предположениях, оптимальное расписание может быть найдено путем решения задачи совершенного паросочетания минимального веса. В случае большего числа ядер процессора показано, что задача является КР-трудной, и предложено несколько приближенных эвристических алгоритмов. Хотя методология из [17] и соответствующие алгоритмы были бы слишком дорогими для использования онлайн, они приемлемы для оценки качества других подходов.

В [93] предлагается новый алгоритм совместного планирования работ с учетом справедливости, основанный на некооперативной игре, для уменьшения промахов кэша L2. Время выполнения работы варьируется в зависимости от того, какие работы выполняются на других ядрах того же процессора, поскольку разные комбинации работ приводят к разным уровням конкуренции в кэше. В [95] определенный объем кэша на процессоре совместно используется его ядрами, а скорость выполнения работы на процессоре зависит от того, какие работы размещены на других ядрах этого процессора. При этом количество работ п равно количеству ядер всех процессоров и все работы запускаются в одно и то же время. В [95] доказано, что эта задача является NP-трудной в общей постановке, но для частного случая (двухъядерный процессор без миграции работ между ядрами) задача разрешима за 0(п2,5 log п). Кроме того в [95] для общей постановки представлен ряд алгоритмов, включая жадный алгоритм, для поиска оптимальных или приближенных решений.

В приложениях для планирования производства также важны постановки задач с переменным временем обработки. Например, в [40] рассматривается задача планирования производства кокса, в которой работы влияют на время выполнения других работ из-за повышения температуры производственной единицы. В [40] строится модель целочисленного программирования, чтобы свести время к минимуму, предлагается несколько эвристических алгоритмов, включая генетический алгоритм, и сравнивается их производительность.

В теории планирования аналогичные постановки задач могут быть найдены в области планирования с контролируемым временем обработки. Модели и методы планирования для случая, когда прерывания допустимы, рассматриваются в [110]. Однако в настоящей главе рассматривается постановка задачи без прерываний. Поскольку работы замедляют друг друга в основном из-за конкуренции за возобновляемые ресурсы (пропускная способность шины данных, кэш), можно сослаться на [67] и [32] для обзоров задач с возобновляемыми ресурсами, где распределение ресурсов может меняться с течением времени. Случай дискретных ресурсов рассматривается в [32], а непрерывные ресурсы рассматриваются в [67]. Последняя статья содержит постановку задачи, аналогичную рассматриваемой в настоящей главе, однако в [67] предполагается, что количество ресурсов, выделяемых для каждой работы, ограничено, но непрерывно и определяется планировщиком в каж-

дый момент времени. В задаче настоящей главы скорость выполнения работ полностью определяется набором совместно запланированных работ на других ядрах (или машинах в традиционной терминологии планирования).

В работе [106] авторы сосредоточились на назначении общих непрерывных ресурсов ядрам, в то время как назначение работ ядрам и их порядок фиксированы. В этом основные отличия от рассматриваемой в данной главе задачи. В [106] также показано, что даже для работ единичной длительности поиск оптимального решения является NP-трудным, если число ядер является частью входных данных. Однако существует алгоритм с полиномиальным временем для любого постоянного числа ядер и работ единичной длительности.

В литературе известно большое количество результатов, посвящённых задаче размещения работ (виртуальных машин) на машинах (физических серверах) [82; 96]. В таких задачах ресурсы, которыми располагают сервера, представлены, как правило, ядрами процессора и объёмом оперативной памяти. Одним из ключевых архитектурных ограничений при решении таких задач является NUMA-архитектура серверов [81], при которой ресурсы распределены по нескольким NUMA-узлам. В частности, для работ с высокими требованиями к ресурсам необходимо обеспечивать сбалансированное распределение нагрузки между несколькими NUMA-узлами, равномерно деля запрашиваемые объёмы ресурсов.

Задача размещения виртуальных машин на сервера является обобщением темпоральной векторной задачи об упаковке в контейнеры (англ. temporal vector bin packing) [23; 44]. В такой задаче каждому элементу (работе) сопоставляется временной интервал активности, в течение которого он потребляет ресурсы (что отражает темпоральный характер задачи), а также вектор требований по нескольким типам ресурсов, таким как ядра процессора и объём оперативной памяти (векторность). В [45] для темпоральной задачи был разработан точный алгоритм, основанный на ветвлении и способный эффективно решать экземпляры размером до 500 элементов. В [57] предложен эвристический алгоритм, основанный на генерации столбцов, который протестирован на более крупных экземплярах, содержащих до 10000 элементов. Для решения задач упаковки также активно применяются приближённые методы, в частности, жадные эвристические алгоритмы, такие как First Fit, Best Fit, Next Fit, Random Fit и их модификации [39; 46; 97]. Для темпораль-

ной векторно задачи упаковки в контейнеры с двумя ресурсами разработаны специализированные методы, включая алгоритм генерации столбцов [102] и генетический алгоритм [104], демонстрирующие высокую эффективность на практических примерах.

1.2 Задача построения расписания для многоядерного процессора с учетом взаимного влияния работ

Неформально рассматриваемая задача состоит в том, чтобы запланировать выполнение работ на ядрах процессора с учетом их замедления при совместном выполнении. Ограничение на порядок выполнения этих работ задается как частичный порядок на множестве работ. Такая постановка не подразумевает, что предшествующие работы как-либо влияют на последующие, например, посредством кэша или температуры процессора. Цель состоит в том, чтобы свести к минимуму время завершения последней работы.

1.2.1 Постановка задачи

Имеется множество работ J = {1,...,п} и т ядер процессора. Прерывание выполнения любой работы запрещено. Работы не меняют ядро в процессе выполнения. На одном ядре не может выполняться более одной работы.

Для каждой работы ] € 3, известно количество единиц времени р^, необходимое ей для полного выполнения в идеальных условиях (т.е. при условии, что вместе с ней не выполняются другие работы).

Введем определения. Конфигурация - это набор работ, выполняющихся одновременно на разных ядрах с учетом частичного порядка на множестве работ (конфигурация не может содержать пару работ, в которой одна из работ должна быть выполнена раньше другой в соответствии с частичным порядком с учетом транзитивности) и ограничений на количество ядер. Множество всех конфигураций обозначим С. Положим, что в нулевой конфигурации ни одна работа не выполняется. На множестве С также задан частичный поря-

Список литературы диссертационного исследования кандидат наук Сахно Мария Юрьевна, 2025 год

Список литературы

1. Еремеев, А. В. Построение расписания для многоядерного процессора с учетом взаимного влияния работ / А. В. Еремеев, М. Ю. Сахно. -DOI: 10.26089/NumMet.v24r108 // Вычислительные методы и программирование. - 2023. - Т. 24, № 1. - С. 115-126.

2. Захарова, Ю. Адаптивный вызов процедур и настройка параметров в эволюционных алгоритмах для задач составления расписаний / Ю. Захарова, М. Сахно // Математическое и компьютерное моделирование

: сб. материалов XI Междунар. науч. конф., посвящ. памяти В.А. Ро-манькова (Омск, 15 марта 2024) / под ред. И. П. Бесценный. - Омск : ОмГУ, 2024. - С. 228-229.

3. Захарова, Ю. Конструктивные алгоритмы для задач составления расписаний с ресурсными ограничениями / Ю. Захарова, М. Сахно // Математическое и компьютерное моделирование: сб. материалов XII Междунар. науч. конф. (Омск, 14 марта 2025) / под ред. И. П. Бесценный. - Омск : ОмГУ, 2025. - С. 124-125.

4. Захарова, Ю. В. Точные алгоритмы для задачи составления расписаний с предписаниями работ на одной машине / Ю. В. Захарова // Дискретные модели в теории управляющих систем : Труды XI международной конференции (Москва и Подмосковье, 26-29 мая 2023 г.) / под ред. С. Ложкин, Д. Романов, В. Подымов. - Москва : МАКС Пресс, 2023. - С. 45-50.

5. Николенко, С. Самообучающиеся системы / С. Николенко, А. Тулупьев. - Москва : Изд-во МЦНМО, 2009. - 288 с. - ISBN 978-5-94057-506-1.

6. Сахно, М. Ю. Адаптивный генетический алгоритм с оптимальной рекомбинацией для задачи составления расписаний с учетом расхода энергии / М. Ю. Сахно. - DOI: 10.15372/SJNM20250307 // Сибирский журнал вычислительной математики. - 2025. - Т. 28, № 3. - С. 327-346.

7. Сахно, М. Ю. Алгоритм списочного типа для размещения виртуальных машин на сервера с учетом NUMA-архитектуры / М. Ю. Сахно //

Прикладная математика и фундаментальная информатика (ПМиФИ). - 2025. - Т. 12, № 3. - С. 9-14.

8. Сахно, М. Экспериментальное исследование методов составления расписаний для многоядерных процессоров / М. Сахно // ФМХ ОмГУ 2022: сб. статей X региональной конф. магистрантов, аспирантов и молодых ученых по физике, математике и химии (Омск, 6-19 июня 2022) / под ред. Ю. В. Захарова, Г. М. Серопян. - Омск : ОмГУ, 2022. - С. 18-21.

9. Свидетельство о государственной регистрации программы для ЭВМ № 2025682254 Российская Федерация. Программа для реализации расписаний при планировании работ на ядрах процессора с учетом их взаимного влияния : № 2025681187 : заявл. 13.08.2025 : опубл. (зарег.) 21.08.2025 / М. Ю. Сахно ; заявитель Сахно Мария Юрьевна. - 1 с.

10. Свидетельство о государственной регистрации программы для ЭВМ № 2025682936 Российская Федерация. Конструктивные эвристические алгоритмы поиска решений для задач составления расписаний в многопроцессорных системах с ресурсными ограничениями : № 2025680891 : заявл. 13.08.2025 : опубл. (зарег.) 28.08.2025 / М. Ю. Сахно ; заявитель Сахно Мария Юрьевна. - 1 с.

11. Свидетельство о государственной регистрации программы для ЭВМ № 2025683991 Российская Федерация. Программа для решения задачи составления расписаний в компьютерных системах с ресурсными ограничениями на основе генетического алгоритма : № 2025680862 : заявл. 13.08.2025 : опубл. (зарег.) 10.09.2025 / М. Ю. Сахно ; заявитель Сахно Мария Юрьевна. - 1 с.

12. Adenso-Diaz, B. Fine-tuning of algorithms using fractional experimental design and local search / B. Adenso-Diaz, M. Laguna. - DOI: 10.1287/o-pre.1050.0243 // Operations Research. - 2006. - Vol. 54, no. 1. - P. 99-114.

13. Aggarwal, C. Optimized crossover for the independent set problem / C. Aggarwal, J. Orlin, R. Tai. - DOI: 10.1287/opre.45.2.226 // Operations Research. - 1997. - Vol. 45. - P. 226-234.

14. Albers, S. On multi-processor speed scaling with migration / S. Albers,

A. Antoniadis, G. Greiner. - DOI: 10.1016/j.jcss.2015.03.001 // Journal of Computer and System Sciences. - 2015. - Vol. 81. - P. 1194-1209.

15. Albers, S. Speed scaling on parallel processors / S. Albers, F. Muller, S. Schmelzer. - DOI: 10.1007/s00453-012-9678-7 // Algorithmica. - 2014. -Vol. 68, no. 2. - P. 404-425.

16. An adaptive multimeme algorithm for designing HIV multidrug therapies / F. Neri, J. Toivanen, G. L. Cascella, Y.-S. Ong. -DOI: 10.1109/TCBB.2007.070202 // IEEE/ACM Transactions on Computational Biology and Bioinformatics. - 2007. - Vol. 4, no. 2. - P. 264-278.

17. Analysis and approximation of optimal co-scheduling on chip multiprocessors / Y. Jiang, X. Shen, J. Chen, R. Tripathi. - DOI: 10.1145/1454115.1454146 // PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques (Toronto, 25-29 Oct. 2008) / ed. by A. Moshovos. - New York : ACM, 2008. - P. 220-229.

18. An optimization spiking neural P system for approximately solving combinatorial optimization problems / G. Zhang, H. Rong, F. Neri, M. J. Perez-Jimenez. - DOI: 10.1142/S0129065714400061 //International Journal of Neural Systems. - 2014. - Vol. 24, no. 5. - Article ID: 1440006.

19. Ansotegui, C. A gender-based genetic algorithm for the automatic configuration of algorithms / C. Ansotegui, M. Sellmann, K. Tierney. -DOI: 10.1007/978-3-642-04244-7_14 // Principles and Practice of Constraint Programming - CP 2009: 15th International Conference, CP 2009 Lisbon, Portugal, September 20-24, 2009 Proceedings. Vol. 5732 LNCS / ed. by I. P. Gent. - Berlin : Springer, 2009. - P. 142-157.

20. Antoniadis, A. Non-preemptive speed scaling / A. Antoniadis, C. C. Huang. - DOI: 10.1007/s10951-013-0312-6 // Journal of Scheduling. -2013. - Vol. 16, no. 4. - P. 385-394.

21. A racing algorithm for configuring metaheuristics / M. Birattari, T. Stut-zle, L. Paquete, K. Varrentrapp. - DOI: 10.5555/2955491.2955494 // GECCO'02: Proceedings of the 4th Annual Conference on Genetic and Evolutionary Computation (New York, 9-13 July 2002) / ed. by W. B.

Langdon [et al.]. - San Francisco : Morgan Kaufmann, 2002.- P. 11-18.

22. Audet, C. Finding optimal algorithmic parameters using derivative-free optimization / C. Audet, D. Orban. - DOI: 10.1137/040620886 // SIAM Journal on Optimization. - 2006. - Vol. 17, no. 3. - P. 642-664.

23. Aydin, N. Multi-objective temporal bin packing problem: An application in cloud computing / N. Aydin, I. Muter, S. Ilker Birbil. - DOI: 10.1016/j.cor.2020.104959 // Computers & Operations Research. - 2020.

- Vol. 121. - Article ID: 104959.

24. Back, T. An overview of parameter control methods by self-adaptation in evolutionary algorithms / T. Back. - DOI: 10.5555/2379195.2379199 // Fundamenta Informaticae. - 1998. - Vol. 35, no. 1-4. - P. 51-66.

25. Balaprakash, P. Improvement strategies for the F-Race algorithm: Sampling design and iterative refinement / P. Balaprakash, M. Birattari, T. Stutzle. - DOI: 10.1007/978-3-540-75514-2_9 // Hybrid Metaheuristics: 4th International Workshop, HM 2007, Dortmund, Germany, October 8-9, 2007, Proceedings. Vol. 4771 LNCS / ed. by T. Bartz-Beielstein [et al.].

- Berlin : Springer, 2007. - P. 108-122.

26. Bampis, E. A note on multiprocessor speed scaling with precedence constraints / E. Bampis, D. Letsios, G. Lucarelli. - DOI: 10.1145/2612669.2612672 // SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (Prague, 23-25 June 2014) / ed. by G. Blelloch. - New York : ACM, 2014. - P. 138-142.

27. Bampis, E. Green scheduling, flows and matchings / E. Bampis, D. Letsios, G. Lucarelli. - DOI: 10.1016/j.tcs.2015.02.020 // Theoretical Computer Science. - 2015. - Vol. 579. - P. 126-136.

28. Bartz-Beielstein, T. Sequential parameter optimization / T. Bartz-Beielstein, C. W. G. Lasarczyk, M. Preuss. -DOI: 10.1109/CEC.2005.1554761 // The 2005 IEEE. Congress on Evolutionary Computation. IEEE CEC 2005. Proceedings: Volume 1 (Edinburgh, 2-5 Sep. 2005) / ed. by D. Come. - Piscataway : IEEE, 2005. - P. 773-780.

29. Bartz-Beielstein, T. The sequential parameter optimization toolbox / T. Bartz-Beielstein, C. Lasarczyk, M. Preuss. - DOI:

10.1007/978-3-642-02538-9_14 // Experimental Methods for the Analysis of Optimization Algorithms / ed. by T. Bartz-Beielstein [et al.]. -Berlin : Springer, 2010. - P. 337-362.

30. Bingham, B. D. Energy optimal scheduling on multiprocessors with migration /B. D. Bingham, M. R. Greenstreet. - DOI: 10.1109/ISPA.2008.128 // ISPA '08: Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications (Sydney, 10-12 Dec. 2008) / ed. by A. Zomaya. - Los Alamitos : IEEE Computer Society, 2008. - P. 153-161.

31. Birattari, M. Tuning metaheuristics: A machine learning perspective. Vol. 197 SCI / M. Birattari. - DOI: 10.1007/978-3-642-00483-4. - Berlin : Springer, 2009. - 221 p. - ISBN 978-3-642-00483-4.

32. Blazewicz, J. Scheduling with discrete resource constraints / J. Blazewicz, N. Brauner, G. Finke // Handbook of Scheduling / ed. by J. Y.-T. Leung. - Boca Raton : CRC Press, 2004. - P. 23-1-23-18.

33. Blum, C. Hybridizations of evolutionary algorithms with Large Neighborhood Search / C. Blum, A. Eremeev, Y. Zakharova. - DOI: 10.1016/j.cosrev.2022.100512 // Computer Science Review. - 2022. - Vol. 46. - Article ID: 100512.

34. Borisovsky, P. Multi-product continuous plant scheduling: combination of decomposition, genetic algorithm, and constructive heuristic / P. Borisovsky, A. Eremeev, J. Kallrath. - DOI: 10.1080/00207543.2019.1630764 // International Journal of Production Research. - 2019. - Vol. 58, no. 9. - P. 267-2695.

35. Bunde, D. Power-aware scheduling for makespan and flow / D. Bunde. -DOI: 10.1007/s10951-009-0123-y // Journal of Scheduling. - 2009. - Vol. 12. - P. 489-500.

36. Cai, X. Minimizing total completion time in two-processor task systems with prespecified processor allocation / X. Cai, C.-Y. Lee, C.-L. Li. -DOI: 10.1002/(SICI)1520-6750(199803)45:2<231::AID-NAV7>3.0.œ;2-9 // Naval Research Logistics. - 1998. - Vol. 45, no. 2. - P. 231-242.

37. Caponio, A. Super-fit control adaptation in memetic differential evolution frameworks / A. Caponio, F. Neri, V. Tirronen. - DOI:

10.1007/s00500-008-0357-1 // Soft Computing - A Fusion of Foundations, Methodologies and Applications. - 2009. - Vol. 13, no. 8. - P. 811-831.

38. Caraffini, F. An analysis on separability for memetic computing automatic design / F. Caraffini, F. Neri, L. Picinali. - DOI: 10.1016/j.ins.2013.12.044 // Information Sciences. - 2014. - Vol. 265. -P. 1-22.

39. Coffman, E. Dynamic bin packing / E. Coffman, M. Garey, D. Johnson.

- DOI: 10.1137/0212014 // SIAM Journal on Computing. - 1983. - Vol. 12, no. 2. - P. 227-258.

40. Coke production scheduling problem: A parallel machine scheduling with batch preprocessings and location-dependent processing times / M. Liu, F. Chu, J. He [et al.]. - DOI: 10.1016/j.cor.2018.12.002 // Computers and Operations Research. - 2019. - Vol. 104. - P. 37-48.

41. Continuous optimization algorithms for tuning real and integer algorithm parameters of swarm intelligence algorithms / Z. Yuan, M. A. Montes de Oca, T. Stutzle, M. Birattari. - DOI: 10.1007/s11721-011-0065-9 // Swarm Intelligence. - 2012. - Vol. 6, no. 1. - P. 49-75.

42. Crama, Y. Local search in combinatorial optimization / Y. Crama, A. W. J. Kolen, E. J. Pesch. - DOI: 10.1007/BFb0027029 // Artificial Neural Networks: An Introduction to ANN Theory and Practice. Vol. 931 LNCS / ed. by P. J. Braspenning [et al.]. - Berlin : Springer, 1995. - P. 157-174.

- ISBN 978-3-540-49283-2.

43. Czyzyk, J. The NEOS Server / J. Czyzyk, M. P. Mesnier, J. J. More. -DOI: 10.1109/99.714603 // IEEE Journal on Computational Science and Engineering. - 1998. - Vol. 5, no. 3. - P. 68-75.

44. De Cauwer, M. The temporal bin packing problem: An application to workload management in data centres / M. De Cauwer, D. Mehta, B. O'Sullivan. - DOI: 10.1109/ICTAI.2016.0033 // Proceedings 2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI) (San Jose, 6-8 Nov. 2016) / ed. by N. Bourbakis [et al.]. - Los Alamitos : IEEE Computer Society, 2016. - P. 157-164.

45. Dell'Amico, M. A branch-and-price algorithm for the temporal bin packing problem / M. Dell'Amico, F. Furini, M. Iori. - DOI:

10.1016/j.cor.2019.104825 // Computers & Operations Research. - 2020. -Vol. 114. - Article ID: 104825.

46. Delorme, M. Bin packing and cutting stock problems: Mathematical models and exact algorithms / M. Delorme, M. Iori, S. Martello. - DOI: 10.1016/j.ejor.2016.04.030 // European Journal of Operational Research.

- 2016. - Vol. 255. - P. 1-20.

47. Doerr, B. Runtime analysis for permutation-based evolutionary algorithms / B. Doerr, Y. Ghannane, M. Ibn Brahim. - DOI: 10.1007/s00453-023-01146-8 // Algorithmica. - 2024. - Vol. 86. - P. 90-129.

48. Drozdowski, M. Scheduling for parallel processing / M. Drozdowski. -DOI: 10.1007/978-1-84882-310-5. - London : Springer, 2009. - 386 p. -ISBN 978-1-84882-310-5.

49. Drugan, M. Reinforcement learning versus evolutionary computation: A survey on hybrid algorithms / M. Drugan. - DOI: 10.1016/j.swevo.2018.03.011 // Swarm and Evolutionary Computation.

- 2019. - Vol. 44. - P. 228-246.

50. Dubois-Lacoste, J. A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems / J. Dubois-Lacoste, M. Lopez-Ibanez, T. Stutzle. -DOI: 10.1016/j.cor.2010.10.008 // Computers & Operations Research. -2011. - Vol. 38, no. 8. - P. 1219-1236.

51. Dubois-Lacoste, J. Improving the anytime behavior of two-phase local search / J. Dubois-Lacoste, M. Lopez-Ibanez, T. Stutzle. - DOI: 10.1007/s10472-011-9235-0 // Annals of Mathematics and Artificial Intelligence. - 2011. - Vol. 61, no. 2. - P. 125-154.

52. Energy-efficient scheduling for parallel real-time tasks based on level-packing / F. Kong, N. Guan, Q. Deng, W. Yi. - DOI: 10.1145/1982185.1982326 // SAC '11: Proceedings of the 2011 ACM Symposium on Applied Computing (Taichung, 21-24 March 2011) / ed. by W. Chu, W. E. Wong. - New York : ACM, 2011. - P. 635-640.

53. Eremeev, A. V. A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem / A. V. Eremeev, Y. V.

Kovalenko. - DOI: 10.1007/s12293-019-00291-4 //Memetic Computing. -2020. - Vol. 12. - P. 23-36.

54. Fair queuing memory systems / K. J. Nesbit, N. Aggarwal, J. Laudon, J. E. Smith. - DOI: 10.1109/MICR0.2006.24 //MICRO 39: Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture (Orlando, 9-13 Dec. 2006) / ed. by T. Conte, H. Zhou. - Los Alamitos : IEEE Computer Society, 2006. - P. 208-222.

55. F-Race and iterated F-Race: An overview / M. Birattari, Z. Yuan, P. Balaprakash, T. Stutzle. - DOI: 10.1007/978-3-642-02538-9_13 // Experimental Methods for the Analysis of Optimization Algorithms / ed. by T. Bartz-Beielstein [et al.]. - 2010. - P. 311-336.

56. From preemptive to non-preemptive speed-scaling scheduling / E. Bampis, A. Kononov, D. Letsios [et al.]. - DOI: 10.1016/j.dam.2014.10.007 // Discrete Applied Mathematics. - 2015. - Vol. 181. - P. 11-20.

57. Furini, F. Matheuristics for the temporal bin packing problem / F. Furini, X. Shen. - DOI: 10.1007/978-3-319-58253-5_19 // Recent Developments in Metaheuristics / ed. by L. Amodeo [et al.]. - Cham : Springer, 2018. -P. 333-345.

58. Gao, K. A review of energy-efficient scheduling in intelligent production systems / K. Gao, Y. Huang, A. Sadollah. - DOI: 10.1007/s40747-019-00122-6 // Complex & Intelligent Systems. - 2020.

- Vol. 6. - P. 237-249.

59. Garey, M. R. Computers and intractability. A guide to the theory of NP-Completeness / M. R. Garey, D. S. Johnson. - San Francisco : W. H. Freeman & Company, 1979. - 338 p. - ISBN 978-0-7167-1045-5.

60. Gen, M. Genetic algorithms and their applications / M. Gen, L. Lin. -DOI: 10.1007/978-1-4471-7503-2_33 // Springer Handbook of Engineering Statistics / ed. by H. Pham. - London : Springer, 2023. - P. 635-674.

61. Gerards, M. E. T. A survey of offline algorithms for energy minimization under deadline constraints / M. E. T. Gerards, J. L. Hurink, P. K. F. Holzenspies. - DOI: 10.1007/s10951-015-0463-8 //Journal of Scheduling.

- 2016. - Vol. 19. - P. 3-19.

62. Greiner, G. The bell is ringing in speedscaled multiprocessor scheduling / G. Greiner, T. Nonner, A. Souza. - DOI: 10.1007/s00224-013-9477-9 // Theory of Computing Systems. - 2014. - Vol. 54, no. 1. - P. 24-44.

63. Herroelen, W. A classification scheme for project scheduling / W. Herroelen, E. Demeulemeester, B. De Reyck. - DOI: 10.1007/978-1-4615-5533-9_1 // Project Scheduling: Recent Models, Algorithms and Applications / ed. by J. W^glarz. - New York : Springer, 1999. - P. 1-26.

64. Hutter, F. Automatic algorithm configuration based on local search / F. Hutter, H. H. Hoos, T. Stutzle. - DOI: 10.5555/1619797.1619831 // AAAI'07: Proceedings of the 22nd national conference on Artificial intelligence - Volume 2 (Vancouver, 22-26 July 2007) / ed. by A. Cohn. -Menlo Park : AAAI Press, 2007. - P. 1152-1157.

65. Hutter, F. Sequential model-based optimization for general algorithm configuration / F. Hutter, H. H. Hoos, K. Leyton-Brown. - DOI: 10.1007/978-3-642-25566-3_40 // Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011, Selected Papers / ed. by C. A. C. Coello. - Berlin : Springer, 2011. - P. 507-523.

66. Ierapetritou, M. G. Effective continuous-time formulation for short-term scheduling: 1. Multipurpose batch processes / M. G. Ierapetritou, C. A. Floudas. - DOI: 10.1021/ie990108r // Industrial & Engineering Chemistry Research. - 1998. - Vol. 37. - P. 4341-4359.

67. Jozefowska, J. Scheduling with resource constraints - continuous resources / J. Jozefowska, J. Weglarz // Handbook of Scheduling / ed. by J. Y.-T. Leung. - Boca Raton : CRC Press, 2004. - P. 24-1-24-15.

68. Kellegoz, T. Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem / T. Kellegoz, B. Toklu, J. Wilson. - DOI: 10.1016/j.amc.2007.10.013 // Applied Mathematics and Computation. - 2008. - Vol. 199, no. 2. - P. 590-598.

69. Kochetov, Y. A. Genetic local search and hardness of approximation for the server load balancing problem / Y. A. Kochetov, A. A. Panin, A. V. Plyasunov. - DOI: 10.1134/S0005117917030043 // Automation and

Remote Control. - 2017. - Vol. 78. - P. 425-434.

70. Kochetov, Y. A. Genetic local search the graph partitioning problem under cardinality constraints / Y. A. Kochetov, A. V. Plyasunov. - DOI: 10.1134/S096554251201006X // Computational Mathematics and Mathematical Physics. - 2012. - Vol. 52. - P. 157-167.

71. Kononov, A. Approximation algorithms for energy-efficient scheduling of parallel jobs / A. Kononov, Y. Kovalenko. - DOI: 10.1007/s10951-020-00653-8 // Journal of Scheduling. - 2020. - Vol. 23. - P. 693-709.

72. Kononov, A. Minimizing total completion time in multiprocessor job systems with energy constraint / A. Kononov, Y. Kovalenko. -DOI: 10.1007/978-3-030-77876-7_18 // Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5-10, 2021, Proceedings. Vol. 12755 LNCS / ed. by P. Pardalos [et al.]. - Cham : Springer, 2021. - P. 267-279. -ISBN 978-3-030-77876-7.

73. Kononov, A. Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion / A. Kononov, Y. Zakharova. - DOI: 10.1007/s10898-021-01115-x // Journal of Global Optimization. - 2022. -Vol. 83. - P. 539-564.

74. Kononov, A. V. Speed scaling scheduling of multiprocessor jobs with energy constraint and total completion time criterion / A. V. Kononov, Y. V. Zakharova // International Journal of Artificial Intelligence. - 2023. -Vol. 21, no. 2. - P. 109-129.

75. Kuhn, H. W. Nonlinear programming / H. W. Kuhn, A. W. Tucker. -DOI: 10.1007/978-3-0348-0439-4_11 // Traces and Emergence of Nonlinear Programming / ed. by G. Giorgi, T. H. Kjeldsen. - Basel : Springer, 2014. - P. 247-258.

76. Lee, C. Scheduling one and two-processor tasks on two parallel processors / C. Lee, X. Cai. - DOI: 10.1023/A:1007501324572 // IIE Transactions. - 1999. - Vol. 31. - P. 445-455.

77. Li, M. An 0(n2) algorithm for computing optimal continuous voltage schedules / M. Li, F. Yao, H. Yuan. - DOI: 10.1007/978-3-319-55911-7_28

// Theory and Applications of Models of Computation: 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings. Vol. 10185 LNCS / ed. by T. Gopal [et al.]. - Cham : Springer, 2017. -P. 389-400.

78. Li, K. Energy efficient scheduling of parallel tasks on multiprocessor computers / K. Li. - DOI: 10.1007/s11227-010-0416-0 // The Journal of Supercomputing. - 2012. - Vol. 60. - P. 223-247.

79. Li, K. Scheduling precedence constrained tasks with reduced processor energy on multiprocessor computers / K. Li. - DOI: 10.1109/TC.2012.120 // IEEE Transactions on Computers. - 2012. - Vol. 61, no. 12. - P. 1668-1681.

80. Lopez-Ibanez, M. Automatic configuration of multi-objective ACO algorithms / M. Lopez-Ibanez, T. Stutzle. - DOI: 10.1007/978-3-642-15461-4_9 // Swarm Intelligence: 7th International Conference, ANTS 2010,Brussels, Belgium, September 8-10, 2010 Proceedings. Vol. 6234 LNCS / ed. by M. Dorigo [et al.]. - Berlin : Springer, 2010. - P. 95-106.

81. Manchanda, N. Non-uniform memory access (NUMA) : tech. rep. / N. Manchanda, K. Anand ; New York University. - 2010. - 4 p.

- URL: https://ru.scribd.com/document/378291456/NUMA-pdf (access date: 26.09.2025).

82. Mann, Z. A. Allocation of virtual machines in cloud data centers - a survey of problem models and optimization algorithms / Z. A. Mann. -DOI: 10.1145/2797211 // ACM Computing Surveys (CSUR). - 2015. -Vol. 48, no. 1. - P. 1-34.

83. Mara, S. A survey of adaptive large neighborhood search algorithms and applications / S. Mara, R. Norcahyo, P. Jodiawan. - DOI: 10.1016/j.cor.2022.105903 // Computers & Operations Research. - 2022.

- Vol. 146. - Article ID: 105903.

84. Maron, O. The racing algorithm: Model selection for lazy learners / O. Maron, A. W. Moore. - DOI: 10.1023/A:1006556606079 // Artificial Intelligence Review. - 1997. - Vol. 11, no. 1-5. - P. 193-225.

85. Martello, S. Knapsack problems: algorithms and computer implementations / S. Martello, P. Toth. - DOI: 10.5555/98124. - New York : John Wiley & Sons, Inc., 1990. - 296 p. - ISBN 978-0-471-92420-3.

86. Martello, S. Lower bounds and reduction procedures for the bin packing problem / S. Martello, P. Toth. - DOI: 10.1016/0166-218X(90)90094-S // Discrete Applied Mathematics. - 1990. - Vol. 28. - P. 59-70.

87. Merkel, A. Resource-conscious scheduling for energy efficiency on mul-ticore processors / A. Merkel, J. Stoess, F. Bellosa. - DOI: 10.1145/1755913.1755930 // EuroSys '10: Proceedings of the 5th European conference on Computer systems (Paris, 13-16 Apr. 2010) / ed. by C. Morin. - New York: ACM, 2010. - P. 153-166. - ISBN 978-1-605-58577-2.

88. Metaheuristics «In the Large» / J. Swan, S. Adriaensen, A. E. I. Brownlee [et al.]. - DOI: 10.1016/j.ejor.2021.05.042 // European Journal of Operational Research. - 2022. - Vol. 297, no. 2. - P. 393-406.

89. Montes de Oca, M. A. An incremental particle swarm for large-scale continuous optimization problems: An example of tuning-in-the-loop (re)design of optimization algorithms / M. A. Montes de Oca, D. Aydin, T. Stutzle.

- DOI: 10.1007/s00500-010-0649-0 // Soft Computing. - 2011. - Vol. 15, no. 11. - P. 2233-2255.

90. Multi-core processor scheduling with respect to data bus bandwidth / A. V. Eremeev, A. A. Malakhov, M. A. Sakhno, M. Y. Sosnovskaya.

- DOI: 10.1007/978-3-030-65739-0_5 // Optimization and Applications: 11th International Conference, OPTIMA 2020, Moscow, Russia, September 28 - October 2, 2020, Proceedings. Vol. 12422 LNCS / ed. by N. Olenev [et al.]. - Cham : Springer, 2020. - P. 55-69.

91. Multiprocessor energy-efficient scheduling with task migration considerations / J. Chen, H. Hsu, K. Chuang [et al.]. - DOI: 10.1109/EM-RTS.2004.1311011 // ECRTS '04: Proceedings of the 16th Euromicro Conference on Real-Time Systems (Catania, 30 June - 2 July 2004) / ed. by L. Lo Bello. - Los Alamitos : IEEE Computer Society, 2004. - P. 101-108.

92. Nannen, V. A method for parameter calibration and relevance estimation in evolutionary algorithms / V. Nannen, A. E. Eiben. - DOI:

10.1145/1143997.1144029 // GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation (Seattle, 8-12 July 2006) / ed. by M. Cattolico. - New York : ACM, 2006. - P. 183-190.

93. Novel fairness-aware co-scheduling for shared cache contention game on chip multiprocessors / Z. Xiao, L. Chen, B. Wang [et al.]. - DOI: 10.1016/j.ins.2020.03.078 // Information Sciences. - 2020. - Vol. 526. - P. 68-85.

94. Oltean, M. Evolving evolutionary algorithms using linear genetic programming / M. Oltean. - DOI: 10.1162/1063656054794815 // Evolutionary Computation. - 2005. - Vol. 13, no. 3. - P. 387-410.

95. Optimal co-scheduling to minimize makespan on chip multiprocessors / K. Tian, Y. Jiang, X. Shen, W. Mao. - DOI: 10.1007/978-3-642-35867-8_7 // Job Scheduling Strategies for Parallel Processing: 16th International Workshop, JSSPP 2012 Shanghai, China, May 25, 2012 Revised Selected Papers. Vol. 7698 LNCS / ed. by W. Cirne [et al.]. - Berlin : Springer, 2013. - P. 114-133.

96. Optimizing virtual machine placement in iaas data centers: taxonomy, review and open issues / H. Talebian, A. Gani, M. Sookhak [et al.] - DOI: 10.1007/s10586-019-02954-w // Cluster Computing. - 2020. - Vol. 23, no. 2. - P. 837-878.

97. Heuristics for vector bin packing : tech. rep. / R. Panigrahy, K. Talwar, L. Uyeda, U. Wieder ; Microsoft Research. - Redmond, 2011. - URL: https://www.labri.fr/perso/eyraud/pmwiki/uploads/Main/ Panigrahy2011-VBPHeuristics.pdf (access date: 26.09.2025).

98. ParamILS: an automatic algorithm configuration framework / F. Hutter, H. H. Hoos, K. Leyton-Brown, T. Stutzle. - DOI: 10.1613/jair.2861 // Journal of Artificial Intelligence Research. - 2009. - Vol. 36. - P. 267-306.

99. Pruhs, K. Getting the best response for your erg / K. Pruhs, P. Uthaisombut, G. Woeginger. - DOI: 10.1145/1367064.1367078 // ACM Transactions on Algorithms. - 2008. - Vol. 4, no. 3. - P. 1-17.

100. Pruhs, K. Speed scaling of tasks with precedence constraints / K. Pruhs, R. van Stee, P. Uthaisombut. - DOI: 10.1007/11671411_24 // Third International Workshop, WAOA 2005, Palma de Mallorca, Spain, October

6-7, 2005, Revised Selected Papers. Vol. 3879 LNCS / ed. by T. Erlebach, G. Persiano. - Berlin : Springer, 2006. - P. 307-319. - ISBN 978-3-540-32208-5.

101. Radcliffe, N. J. The algebra of genetic algorithms / N. J. Radcliffe. - DOI: 10.1007/BF01531276 // Annals of Mathematics and Artificial Intelligence.

- 1994. - Vol. 10, no. 4. - P. 339-384.

102. Ratushnyi, A. A column generation based heuristic for a temporal bin packing problem / A. Ratushnyi, Y. Kochetov. - DOI: 10.1007/978-3-030-77876-7_7 // Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5--10, 2021, Proceedings. Vol. 12755 LNCS / ed. by P. Pardalos [et al.]. - Cham : Springer, 2021. - P. 96-110. - ISBN 978-3-030-77876-7.

103. Reeves, C. R. Genetic algorithms for the operations researcher / C. R. Reeves. - DOI: 10.1287/ijoc.9.3.231 // INFORMS Journal of Computing.

- 1997. - Vol. 9, no. 3. - P. 231-250.

104. Sakhno, M. A grouping genetic algorithm for the temporal vector bin packing problem / M. Sakhno. - DOI: 10.1109/OPCS59592.2023.10275770 // Proceedings 2023 19th International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS) (Novosibirsk, Moscow, Almaty, 14-22 Aug. 2023) / ed. by A. Rodionov. - Los Alamitos : IEEE Computer Society, 2023. - P. 94-99.

105. Sakhno, M. Investigation of operators and parameters in evolutionary algorithms for one scheduling problem with resource constraints / M. Sakhno // MOTOR 2024: сборник тезисов XXIII Международной конференции «Теория математической оптимизации и исследование операций» (Омск, 30 июня - 06 июля 2024) / под ред. Ю. В. Захарова, П. А. Борисовский. - Омск : ОмГУ, 2024. - С. 81.

106. Scheduling shared continuous resources on many-cores / E. Althaus, A. Brinkmann, P. Kling, F. M. Heide. - DOI: 10.1007/s10951-017-0518-0 // Journal of Scheduling. - 2018. - Vol. 21. - P. 77-92.

107. Shabtay, D. Parallel machine scheduling with a convex resource consumption function / D. Shabtay, M. Kaspi. - DOI: 10.1016/j.ejor.2004.12.008

// European Journal of Operational Research. - 2006. - Vol. 173, no. 1.

- P. 92-107.

108. Shahrokhi, F. The maximum concurrent flow problem / F. Shahrokhi, D. W. Matula. - DOI: 10.1145/77600.77620 // Journal of the ACM. - 1990.

- Vol. 37, no. 2. - P. 318-334.

109. Shioura, A. Machine speed scaling by adapting methods for convex optimization with submodular constraints / A. Shioura, N. Shakhlevich, V. Strusevich. - DOI: 10.1287/ijoc.2017.0758 // INFORMS Journal on Computing. - 2017. - Vol. 29, no. 4. - P. 724-736.

110. Shioura, A. Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches / A. Shioura, N. V. Shakhlevich, V. A. Strusevich. - DOI: 10.1016/j.ejor.2017.08.034 // European Journal of Operational Research.

- 2018. - Vol. 266, no. 3. - P. 795-818.

111. Slowik, A. Evolutionary algorithms and their applications to engineering problems / A. Slowik, H. Kwasnicka. - DOI: 10.1007/s00521-020-04832-8 //Neural Computing & Applications. -2020. - Vol. 32. - P. 12363-12379.

112. Smit, S. K. Beating the 'world champion' evolutionary algorithm via REVAC tuning / S. K. Smit, A. E. Eiben. - DOI: 10.1109/CEC.2010.5586026 // Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2010 (Barcelona, 18-23 July 2010) / ed. by P. Sobrevilla. - Piscataway : IEEE, 2010. - P. 1-8.

113. Smit, S. K. Comparing parameter tuning methods for evolutionary algorithms / S. K. Smit, A. E. Eiben. - DOI: 10.5555/1689599.1689651 // CEC'09: Proceedings of the Eleventh conference on Congress on Evolutionary Computation (Trondheim, 18-21 May 2009) / ed. by A. Tyrrell. -Piscataway : IEEE, 2009. - P. 399-406.

114. Speed scaling on parallel processors with migration / E. Angel, E. Bampis, F. Kacem, D. Letsios. - DOI: 10.1007/s10878-018-0352-0 // Journal of Combinatorial Optimization. - 2019. - Vol. 37, no. 4. - P. 1266-1282.

115. Sutton, R. Reinforcement learning: An introduction / R. Sutton, A. Barto. - Cambridge: MIT Press, 1998. - 552 p. - ISBN 978-0-262-03924-6.

116. The irace package: Iterated racing for automatic algorithm configuration / M. Lopez-Ibanez, J. Dubois-Lacoste, L. Perez Caceres [et al.]. - DOI: 10.1016/j.orp.2016.09.002 // Operations Research Perspectives. - 2016. -Vol. 3. - P. 43-58.

117. Uxlfoundation oneAPI Threading Building Blocks (oneTBB): site. - URL: https://github.com/uxlfoundation/oneTBB (access date: 19.09.2025).

118. Xhafa, F. Metaheuristics for scheduling in distributed computing environments / F. Xhafa, A. Abraham. - DOI: 10.1007/978-3-540-69277-5. -Berlin : Springer, 2008. - 364 p. - ISBN 978-3-540-69277-5.

119. Yagiura, M. The use of dynamic programming in genetic algorithms for permutation problems / M. Yagiura, T. Ibaraki. - DOI: 10.1016/0377-2217(94)00301-7 // European Journal of Operational Research. - 1996. - Vol. 92, no. 2. - P. 387-401.

120. Yao, F. A scheduling model for reduced CPU energy / F. Yao, A. Demers, S. Shenker. - DOI: 10.1109/SFCS.1995.492493 // Proceedings of IEEE 36th Annual Foundations of Computer Science (Milwaukee, 23-25 Oct. 1995) / ed. by A. Borodin. - Los Alamitos : IEEE Computer Society, 1995. - P. 374-382.

121. Zakharova, Y. V. Population local search for single processor energy efficient scheduling problem / Y. V. Zakharova. - DOI: 10.1007/978-3-031-81241-5_35 // Numerical Computations: Theory and Algorithms: 4th International Conference, NUMTA 2023, Pizzo Calabro, Italy, June 14-20, 2023, Revised Selected Papers, Part I / ed. by Y. D. Sergeyev [et al.]. - Berlin : Springer, 2025. - P. 400-408.

122. Zakharova, Y. V. Adaptive genetic algorithm with optimized operators for scheduling in computer systems / Y. V. Zakharova, M. Y. Sakhno. -DOI: 10.1007/978-3-031-57808-3_23 // Intelligent Information Processing XII: 13th IFIP TC 12 International Conference, IIP 2024, Shenzhen, China, May 3-6, 2024, Proceedings. Vol. 703 IFIPAICT / ed. by Z. Shi [et al.]. -Cham : Springer, 2024. - P. 317-328.

123. Zakharova, Y. V. Complexity and heuristic algorithms for speed scaling scheduling of parallel jobs with energy constraint / Y. V. Zakharova, M. Y. Sakhno. - DOI: 10.1016/j.cam.2024.116254 // Journal of Computational

and Applied Mathematics. - 2025. - Vol. 457. - Acticle ID: 116254.

124. Zakharova, Y. Heuristics with local improvements for two-processor scheduling problem with energy constraint and parallelization / Y. Zakharova, M. Sakhno // Book of Abstracts of the 4th International Conference and Summer School Numerical Computations: Theory and Algorithms (Calabria, 14-20 June 2023) / ed. by Y. D. Sergeyev [et al.]. -Calabria : Universita della Calabria, 2023. - P. 180.

125. Zakharova, Y. V. Heuristics with local improvements for two-processor scheduling problem with energy constraint and parallelization / Y. V. Zakharova, M. Y. Sakhno. - DOI: 10.1007/978-3-031-81241-5_17 // Numerical Computations: Theory and Algorithms: 4th International Conference, NUMTA 2023, Pizzo Calabro, Italy, June 14-20, 2023, Revised Selected Papers, Part I. Vol. 14476 LNCS / ed. by Y. D. Sergeyev [et al.]. - Cham : Springer, 2025. - P. 241-256.

126. Zakharova, Y. Integer programming models for multi-processor scheduling of parallelizable jobs with resource-dependent durations / Y. Zakharova, M. Sakhno // XIII International Conference on Optimization Methods and Applications «OPTIMIZATION AND APPLICATIONS (OPTIMA-2022)». Petrovac, Montenegro, September 26-30, 2022. BOOK OF ABSTRACTS / ed. by V. Malkova. - Moscow : FRC CSC RAS, 2022. - P. 79.

127. Zakharova, Y. Structure of schedules for problems with parallelizable jobs / Y. Zakharova, M. Sakhno // XXII International Conference «Mathematical Optimization Theory and Operations Research» (MOTOR 2023). Abstracts (Ekaterinburg, 2-8 July 2023) / ed. by M. Khachay [et al.]. -Ekaterinburg : UMC UrFU, 2023. - P. 54.

128. Zhuravlev, S. Addressing shared resource contention in multicore processors via scheduling / S. Zhuravlev, S. Blagodurov, A. Fedorova. -DOI: 10.1145/1736020.1736036 // ASPLOS XV: Proceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems (Pittsburgh, 13-17 March 2010) / ed. by J. C. Hoe. - New York : ACM, 2010. - P. 129-142. - ISBN 978-1-605-58839-1.

ПРИЛОЖЕНИЕ А Доказательство NP-трудности задачи Р 2\sizej ,energy\Y2 Cj

Мы рассматриваем следующую задачу упорядоченного разбиения в следующей постановке:

Пусть задан упорядоченный набор А = а1,а2,... ,о2п0 положительных целых чисел, такой что X^gAai = 2С, ai < ai+1, i = 1,...,2п0 — 1 и а2г+1 > 3a2i для i = 1,..., п0 — 1.Необходимо определить, существует ли такое разбиение множества А на два подмножества А1 и А2, что

ai = ^2 ai = с, \^i\ = \^2\ = по,

a-i&Ai aieA2

и подмножество А1 содержит ровно один элемент из каждой пары a,2i—i, a,2i, i = 1,... ,щ.

Лемма 2. Задача упорядоченного разбиения является NP-трудной.

Доказательство. Рассмотрим классическую задачу разбиения множества (Partition Problem) с множеством элементов В = {Ь1,Ь2,... ,ЬП0}. Необходимо определить, существует ли разбиение множества В на два подмножества В1 и В2 такое, что

Еb' = Z

heB- heB2

Положим

a1 = 1,

а,2i = a,2i—1 + bt,i = 1,... ,щ, a-2i+1 = 3(a-2i + 1), i =1,...,no — 1.

Тогда

п0 п0

= ^2 a2 i—1 + ^ bi = ^2 a2i—1 + ^2 bi = ^2 ai i eAi i=1 bieB1 i=1 bi eB2 i eA2

тогда и только тогда, когда

E b> = £ b:

heBi heB2

□

Теорема 9. Задача Р 2\sizej ,епегду\^2 является ЫР-трудной.

Доказательство. Доказательство КР-трудности основано на полиномиальном сведении задачи упорядоченного разбиения к распознавательной версии рассматриваемой задачи.

Построим экземпляр задачи с п\ = 2п0 работами, требующими одного процессора, и одной работой, требующей два процессора, п = 2щ + 1. Положим: V2j-1 = a2j-l(no-з + 3)1, size2j-l = 1 и ^ = a2j(щ-] + §)1, size2j = 1

а—1

для ] = 1,... ,п0 и У2п0+1 = 2~ М, size2nо+1 = 2. Здесь М это большая константа,

М := шах | (2по + 1) 0 а,2п0; ~ 3 + 0 (а23 + «2-1) | + 1.

j=l

Зададим ограничение на энергию Е = 1(п0 — 3 + §-1 + )+ ^. Отметим, что объёмы ^ возрастают, поскольку а^- возрастают, и +1 =

— (п—Ш " > 31 > 1.

о-2з \п—+3/2 )

Установим пороговое значение Ф = Е.

Покажем, что допустимое расписание Б с Cj(Б) ^ Ф существует тогда и только тогда, когда задача упорядоченного разбиения имеет положительный ответ.

Рассмотрим расписания, в которых работа 2п0 + 1 выполняется последней. Оценим снизу сумму времён завершения работ для таких расписаний при заданной последовательности п = (п1,... ,п2по, 2п0 + 1) работ (см. рис. А.1):

по 1 по

Е (п0 - Э + 1) (Рп2о—1 + Ръ,) + 2 1 + Рп21) + Р2по+1 ^ (А.1)

j=1 j=1

Е(Р^и + р\ГУ5) + 2 • р2—0°+^а = Е. (А.2) j=1 ^ J

Представленная модель имеет линейную целевую функцию и выпуклое

ограничение на потребление энергии. Используя необходимые и достаточные

условия Каруша—Куна—Таккера [75], получаем оптимальное решение.

1

3^ -1

Рп21 = ^0 - 3 + 0 • • G,

Р1 Р4 Р6 Р7 Р9

Р2 Рз Р5 Р8

Рисунок А.1 — Иллюстративный пример к расписанию, в котором двухпроцессорная задача выполняется последней

Р1 Р4

Р2

Р5

Р3

Р9

Р7

Рб

Р8

Рисунок А.2 — Иллюстративный пример к расписанию, в котором двухпроцессорная задача не является последней

С —

Р*

=(п°— *+2)

( V2по+1 \

V 2 )

• К*,-- 1 • G,

Р2по+1 — 2

■с,

а-1

ЕП= 1 Ц - 3 + I) " (^ + Уп2з-1) + ^2по+12

Е

1-а \ а-1

Оптимальное значение целевой функции (нижняя оценка) равняется

\

1 \ «Л

1 —а \ \

а— 1 1 \

ЕП= 1 (П° - 3 + 2) " + Уп2— ) + У2по+1^

а—1

Е

(А.3)

/

Последовательность {п° — ] + 2) убывает, поэтому упорядочивание задач по неубывающим значениям работы У^ даёт нижнюю оценку:

по

по

(п° — 1 + 1) (а23—1 + а^) + 2 1 + ау) + м — ф.

3=1 3=1

Заметим, что в этом случае С — 1, ^ — aj для ] — 1,..., 2п°. Следовательно, допустимое расписание $, в котором последней работой является

1

1

2n0 + 1, имеет Е Cj (S) ^ Ф тогда и только тогда, когда задача упорядоченного разбиения имеет положительный ответ.

Теперь покажем, что если задача 2п0 + 1 не является последней в расписании S, то для такого расписания Е Cj(S) > Ф.

Рассмотрим расписание следующей структуры: п — к однопроцессорных работ с объёмами V- выполняются на одном процессоре, п + к однопроцессорных работ с объёмами V" — на другом процессоре, и всего I ^ 1 однопроцессорных работ выполняются после работы 2п0 + 1. Нижнюю оценку целевой функции для такого расписания можно вычислить, решив следующую выпуклую задачу:

по—к щ+к

Ё К — к — j + 1) pj + Е (no + к — j + 1) pj + (l + 1)р2по+1 ^ min, (А.4) j=i j=i

по —к по+к ч а

£ (P'j)1—а(У])а + Е $)1—а(^")а + 2 ■ Äi+i (^Г1) = Е. (А.5)

Здесь переменные р" (р") соответствуют временам выполнения работ на одном (соответственно, другом) процессоре.

Используя условия Каруша—Куна—Таккера, мы находим оптимальное решение задачи:

р'3 = (щ - к - з + 1)-1 • V" • С,з = 1,... ,по - к,

р". = (по + к - 3 + 1)-1 • V" • С,з = 1,...,по + к,

Р2п0+! = 21 • (^) • (/ + 1)- • С,

G =

(п0 к а-1 п0+к , _ , а-1

— к

Е ("о — к — 3 + 1)^ V> + £ (по + к — 3 + 1)^ Vj' j=i j=i

Е

\

+ ^2по+1 (щ)

1

1—а \ а-1

Е

Целевая функция равна:

к («0 — к — 3 + 1) ^ V! + Еп=+к ("о + к — з + 1)а-1 V!

Е

+ (А.6)

, 2 N — \ ^ а—1

У2п0+1 Ci+2^; а) Е

/

Рассмотрим следующее расписание: времена выполнения работы равны pj, , р2по+1, п — к работ с длительностями pj выполняются на одном процессоре, п + к работ с длительностями р" — на другом процессоре, а работа 2по + 1 с длительностью р2по+1 является последней. Тогда сумма времени завершения равна

по—к по+к

¿ (по — к — j + 1) рj + ¿ (по + к — j + 1) р"+ 3=1 3=1

п—к п+к

тах{^ р'з ; ^ Pj } + Р2п0+ъ (А.7)

=1 =1

Мы можем показать, что (А.7)<(А.4).

Действительно, это следует из свойствар2по+1 > max{X]j—i PjPj} ^ max{Y2j—i Pj1 Pj}/l при l ^ 1 (см. лемму ниже).

Таким образом, расписания, в которых работа 2п0 + 1 не является последней, имеют большую целевую функцию, чем расписания, в которых эта работа — последняя. Следовательно, если работа 2п0 + 1 не является последней в расписании S, то такое расписание имеет Cj (S) > Ф. □

Лемма 3. Р2по+1 > max jPj, Y^t! Р"} ■

Доказательство. Легко видеть, что max{pj ,р"} ^ У2по • G'.

Из определения следует, что М > (2п0 + 1)(|) " а2по, следовательно

i

1 /3\ а

М> (2по)(1 + 1)W 2) «2по,

21 ^(/ + 1)—1 > (2по) (2) 1 «2п

2 V- ■ ' V--W "2по:

Р2по+1 > (2по) • У2по • G',

(п—k п+к \

Р2по+1 > (2по) • ma^{pj ,р'"} ^ m^^pj.

=1 =1

□

+

ПРИЛОЖЕНИЕ Б Акт о внедрении

НиАУУЕ!

Общество с ограниченной ответственностью «ТЕХКОМПАНИЯ ХУАВЭЙ»

121614, г. Москва, ул. Крылатская, д.17, корп.2 Тел.: [phone] Факс: [phone] ОГРН 1027739023212, ИНН 7714186804

г. Москва, г. Москва, №М>24122024/2

Аспиранту ИМ СО РАН М.Ю. Сахно

АКТ

о внедрении результатов диссертационного исследования М.Ю. Сахно

«Математические модели и списочные алгоритмы для построения расписаний в многопроцессорных системах с ресурсными ограничениями»

Настоящий акт подтверждает внедрение результатов диссертационной работы Сахно Марии Юрьевны «Математические модели и списочные алгоритмы для построения расписаний в многопроцессорных системах с ресурсными ограничениями», выполненной в Федеральном государственном бюджетном учреждении науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук (ИМ СО РАН) и представленной на соискание ученой степени кандидата технических наук по специальности 1.2.2. «Математическое моделирование, численные методы и комплексы программ».

При анализе системы планирования работ для серверов облачных ресурсов в ООО «Техкомпания Хуавэй» применяются разработанные в указанной диссертации конструктивные алгоритмы и используются выявленные свойства расписаний при различных структурных свойствах тестовых примеров. Указанные результаты получены в рамках работ по договору № УВШ020075031 между ООО «Техкомпания Хуавэй» и ИМ СО РАН.

Акт составил к.ф.-м.н. Шмелькин Дмитрий Альфредович

Директор лаборатории математического

моделирования и оптимизации алгоритмов /У/ж

Московского научно-исследовательского центра уФ^—""

ООО «Техкомпания Хуавей»

Утверждено

Директор Московского научно-исследовательского центра ООО «Техкомпания Хуавей»

ПРИЛОЖЕНИЕ В

Свидетельства о государственной регистрации программы для

ЭВМ

1Р©(0еИ®(0ЕДЖ МДИРАЩШШ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2025682254

Программа для реализации расписаний при планировании работ на ядрах процессора с учетом их взаимного влияния

Правообладатель: СаХНО Мария Юрьевна (Ки)

\втор(ы

: Сахно Мария Юрьевна (Ки)

Заявка № 2025681187

Дата поступления 13 августа 2025 Г.

Дата государственной регистрации

в реестре программ для эвм 21 августа 2025 ,

Ш>жжжжжжжжжжжж® жжжжжжжжжжжжжжжжжжж^й

теОТЖЙСЕАЖ ФЖДШРАЩШШ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2025682936

жШШШШ _

Шй

шшшш

ХЛ

Конструктивные эвристические алгоритмы поиска решении для задач составления расписании в многопроцессорных системах с ресурсными

ограничениями

.: УЛУШЯ

ль: Сахно Мария Юрьевна ^Ц)

■■.■•■........

Автор(ы):

Сахно Мария Юрьевна (ЯЦ)

шшшш

ЩШШШ

;. : ■ : .. ■ 7 ... ..

: ; . ;

: :

Заявка № 2025680891 Дата поступления 13 августа 2025 Г.

тт -

Дата государственной регистрации

в реестре программ для эвм 28 августа 2025 г.

: : • : : ■

Руководитель Федеральной службы

::.:: : : :

В шШШШ

■у ■' у..:-. .................

по интеллектуальной собственности

...... ::.:.:...:.:,.;,...

ДОКУМЕНТ ПОДПИСАН'ЭПЕКТРОННОЙ ПОДПИСЬЮ

Сертификат 0692е7с1а630(М5А<2Ш670Ьса2026 Владелец Зубов Юрий Сергеевич

Действителен с по 03.10.2025

.-..-.;,.-• ....... ■ -..-Л- . ,..-....-.;-,•. ....

-

Ю.С. Зубов

теОТЖЙСЕАЖ ФЖДШРАЩШШ

жжжжжж

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

■

■ . ,,.. . : . : : ■.■ ...

№ 2025683991

Ш.Ш

III

II

«Программа для решения задачи составления

расписании в компьютерных системах с ресурсными ограничениями на основе генетического алгоритма»

/ ; : : : V : :'.