Исследование алгоритмической сложности построения Парето-множества для принятия решения при распределении ресурсов вычислительных систем

Лицензировано по CC BY 4.0. Чтобы посмотреть копию этой лицензии, посетите

Вестник Пермского университета. Математика. Механика. Информатика. 2026. № 2(73). С. 88-103. DOI: 10.17072/1993-0550-2026-2-88-103.

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

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

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

Вместе с тем применение Парето-оптимизации в системах реального времени сопряжено с серьезной вычислительной проблемой. Базовый алгоритм построения Парето-множества основан на попарном сравнении всех кандидатов по каждому из рассматриваемых критериев. При увеличении числа кандидатов, характерном для крупных облачных платформ, данная зависимость становится узким местом системы, ограничивая применимость Парето-оптимизации в условиях жестких временных ограничений. Указанная проблема обусловливает необходимость исследования и применения методов снижения вычислительной сложности данного этапа.

Вопросы повышения эффективности алгоритмов Парето-оптимизации нашли отражение в ряде научных работ. Алгоритм Кунга [3], основанный на стратегии "разделяй и властвуй", позволил снизить сложность нахождения максимальных векторов до O(n log n) для двухкритериального случая. Широко применяемый алгоритм NSGA-II [4, 5] ввел эффективную процедуру недоминируемой сортировки с применением операции сравнения рангов, ставшую основой для последующих разработок. В работе [6] предложен алгоритм ENS (Efficient Non-dominated Sorting), достигающий существенного ускорения за счет сокращения числа выполняемых сравнений. Такие алгоритмы, как ENS и другие методы недоминируемой сортировки, подробно рассмотрены в обзорных работах [7], где они классифицированы по принципам построения. Алгоритмы Rank Sort [8, 9] используют битовый параллелизм и пересечения множеств, обеспечивая дополнительное ускорение по сравнению с предшествующими методами. С. Е. Кривобокова и В. А. Родин в своей статье [10] затрагивают алгоритмические сложности построения множества Парето, связанные с конфигурацией массива точек, и предлагают авторский алгоритм для их решения. Тем не менее применение указанных подходов в контексте предсказательного распределения ресурсов в облачных системах остается недостаточно исследованным.

Целью настоящей статьи является исследование вычислительной сложности построения Парето-множества в задаче многокритериального предсказательного распределения ресурсов и анализ методов ее снижения. Для достижения поставленной цели решаются следующие задачи:

• 1)    построить и исследовать зависимости алгоритмической сложности базового алгоритма построения Парето-множества от основных параметров: количества узлов-кандидатов и числа критериев;

• 2)    проанализировать известные подходы к снижению алгоритмической сложности построения Парето-множества, оценить вычислительную сложность построения Парето-множества с их применением;

• 3)    провести экспериментальное исследование на программной имитационной модели для сравнения ранее рассмотренных подходов между собой и с базовым алгоритмом;

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

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

Настоящая статья является продолжением работы [11], в которой был предложен предсказательный метод распределения ресурсов в вычислительных системах на основе многокритериальной модели принятия решений. В указанной работе один из ключевых этапов метода – построение множества Парето-оптимальных решений ( P ), однако вычислительная сложность данного этапа и возможности ее снижения не исследовались. Настоящая статья восполняет этот пробел. Для обеспечения преемственности на рис. 1 приводится формализации системы в объеме, необходимом для дальнейшего анализа.

Рис. 1. Система распределения ресурсов

Построение множества P реализовано методом полного попарного сравнения. Вычислительная сложность такого алгоритма определяется следующим образом. Число пар п\п-1)

узлов, подлежащих сравнению, составляет       , где n – размер множества кандида тов. Для каждой пары выполняется сравнение по m критериям. Тогда, общее число элементарных операций сравнения равно:

П- (п — 1)

-----т ^ 0(п2 ■ т).

При небольшом числе узлов данная сложность не является критичной. Однако в реальных вычислительных системах число кандидатов n может быть существенно больше: в крупных облачных кластерах количество доступных узлов достигает сотен и тысяч. В таких условиях квадратичная зависимость от n становится узким местом алгоритма, ограничивая применимость Парето-оптимизации в системах реального времени.

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

Базовый алгоритм построения Парето-множества

Базовый алгоритм построения Парето-множества основан на методе полного попарного сравнения всех узлов-кандидатов. Он принимает на вход множество узлов U = { u ₁, u ₂, …, u ₙ} с вычисленными кортежами критериев C ( u ⱼ, Z ) и возвращает подмножество P с U , содержащее все недоминируемые узлы:

^базовый (п, т)   0(п • т).

Алгоритм 1 . Первоначально все узлы считаются кандидатами в Парето-множество. Для каждой упорядоченной пары ( uᵢ , uⱼ ) выполняется проверка: доминирует ли uᵢ узел uⱼ . Если по результатам сравнения всех m критериев uᵢ не хуже uⱼ по всем критериям и строго лучше хотя бы по одному, узел uⱼ исключается из P . По завершении двойного цикла в P остаются только недоминируемые узлы.

Зависимость от параметров . При фиксированном числе критериев m сложность алгоритма растет квадратично по числу узлов n . При фиксированном n сложность растет линейно по m . На практике m , как правило, невелико (в рассматриваемой задаче m = 3), поэтому определяющим параметром является n . В таблице 1 приведены оценки числа операций сравнения для разных значений n при m = 3.

Таблица 1. Число операций сравнения базового алгоритма при m = 3

n узлов	O ( n 2 · m )
10	270
50	7 350
100	29 700
500	747 000
1000	2 997 000
5000	74 970 000

Как видно из табл.1, уже при n = 500 число операций превышает 700 тысяч, а при n = 5 000 достигает порядка 75 миллионов. При высокой интенсивности входящего потока задач, когда Парето-множество строится при поступлении каждой новой задачи, суммарные затраты могут стать критичными.

Оценка времени выполнения. Пусть т - среднее время выполнения одной элементарной операции сравнения на целевой вычислительной платформе. Тогда ожидаемое время построения Парето-множества базовым алгоритмом:

?базовый(п,т) = т • п(п — 1) • т.

При известной интенсивности входящего потока задач λ (задач в единицу времени) среднее процессорное время, затрачиваемое на этап Парето-оптимизации в единицу времени:

L = Л • т • п(п — 1) • т.

Условие применимости базового алгоритма в системе реального времени: L < 1, то есть суммарная нагрузка от этапа Парето-оптимизации не должна превышать пропускную способность одного процессорного ядра. При нарушении этого условия требуется применение методов снижения вычислительной сложности.

Методы ускорения построения Парето-множества

Снижение вычислительной сложности при построении Парето-фронта является актуальной задачей. Один из подходов, называемый "прореживанием" (pruning), предполагает сокращение множества решений еще до или в процессе сравнения. Обзор таких методов представлен в работе [12], где они классифицированы по способу отбора репрезентативных точек.

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

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

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

Здесь параметр 0 регулирует жесткость фильтрации: при 0 = 1 сохраняются только узлы с минимальным значением C ключ , при 0 ^ ® фильтрация вырождается в базовый алгоритм. На практике 0 выбирается в зависимости от допустимой потери качества решения.

Алгоритм 2 . Предварительная фильтрация по ключевому критерию.

Вход: множество узлов U , кортежи критериев C ( ц ), ключевой критерий C ключ , порог 0 > 1.

Выход: отфильтрованное множество U * с U, Парето-множество P .

Здесь базовый алгоритм, применяемый к отфильтрованному множеству U *.

Анализ вычислительной сложности . Пусть после фильтрации в U * остается n ' узлов, где n' = а • n , а G (0, 1] - коэффициент сохранения. Тогда сложность метода:

^фильтр(п,т) = О(п) + О(п'2 • т) = О(п) + 0(а2п2 • т).

Первое слагаемое - однократный проход по U для вычисления минимума и формирования U *. Второе слагаемое - базовый алгоритм на U *.

При а < 1 достигается ускорение относительно базового алгоритма:

° фильтр

^-базовый    ^  _ ¹

^-фильтр     ^ ²    ®²

Например, если фильтрация отсеивает половину узлов ( а = 0,5), ускорение составляет приблизительно в 4 раза. Если отсеивается 80% узлов ( а = 0,2), ускорение достигает 25 раз.

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

Ранняя остановка при попарном сравнении

В базовом алгоритме для каждой пары ( u, , uj ) сравнение всегда выполняется по всем m критериям, даже если факт отсутствия доминирования может быть установлен раньше. Метод ранней остановки модифицирует внутренний цикл по критериям: как только в процессе проверки обнаруживается, что доминирование невозможно, сравнение пары прекращается досрочно.

Условие досрочного завершения: если при проверке критерия C k обнаружено, что C k ( Ui ) >  C k ( Uj ), то узел Ui не может доминировать Uj (поскольку нарушено условие - не хуже по всем критериям). Дальнейшая проверка оставшихся критериев для данной пары не имеет смысла.

Алгоритм 3. Построение Парето-множества с ранней остановкой.

Вход: множество узлов U , кортежи критериев C ( и, ), число критериев m.

Выход: Парето-множество P .

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

Анализ вычислительной сложности. Худший случай остается прежним: O ( n ² • m). Он реализуется, когда все узлы несравнимы (никто не доминирует никого) и нарушение условия доминирования обнаруживается лишь на последнем критерии.

Средний случай. Пусть критерии проверяются в некотором порядке. Если значения критериев распределены независимо и равномерно, то вероятность того, что узел ui не хуже Uj по первому критерию, равна приблизительно 0.5. Ожидаемое число проверяемых критериев до обнаружения нарушения:

т

Жтоп^ ^к к=1

0,5к-1 • 0,5 « 2.

В среднем для каждой пары проверяется около 2 критериев вместо m . Ожидаемое число операций:

^ранний выходС7, т) ~ П(П 1) • £'[кСтоп]     0(71 ), при m >> 2, что дает преимущество в m/2 раз по сравнению с базовым алгоритмом.

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

Корректность метода. Ранняя остановка не изменяет результат алгоритма: множество P , возвращаемое алгоритмом 3, идентично множеству P алгоритма 1. Метод является точным и не вносит никакого приближения.

Инкрементальное построение Парето-множества

В предыдущих двух методах Парето-множество строится заново при каждом вызове алгоритма. Инкрементальный подход применим в ситуации, когда множество кандидатов U пополняется поэлементно - например, когда характеристики узлов обновляются последовательно по мере поступления данных о текущей загрузке.

Идея метода: поддерживать актуальное Парето-множество P , добавляя в него новые узлы по одному. При поступлении нового узла и нов выполняется его проверка относительно текущего P :

• -    если и нов доминируется хотя бы одним элементом P , он не включается в P ;

• -    если и нов доминирует некоторые элементы P , они исключаются из P , а и нов добавляется;

• -    если и нов несравним со всеми элементами P , он добавляется в P без исключений.

Алгоритм 4 . Инкрементальное построение Парето-множества.

Вход: новый узел и нов , текущее Парето-множество P , число критериев m.

Выход: обновленное Парето-множество P .

Полное построение Парето-множества с нуля выполняется последовательным применением алгоритма 4 ко всем n узлам:

Анализ вычислительной сложности:

Однократное добавление узла. При добавлении и нов в P размером | P | = p выполняется не более p сравнений (по одному на каждый элемент P ), каждое из которых включает не более m проверок критериев. Сложность одного шага:

^Т инк.шаг     О(.Р • ^т).

Полное построение с нуля. При последовательном добавлении n узлов размер P в общем случае изменяется. В лучшем случае | P | = 1 на каждом шаге (один узел доминирует всех предыдущих) - сложность: O ( n • m ).

В худшем случае | P | растет до n (все узлы несравнимы) - сложность:

п

Т инк = ^ i

^(п+1)

• т = т------= О(гг • т),

1 = 1

что совпадает с базовым алгоритмом. При этом асимптотика в худшем случае не улучшается, однако на практике | P | <<  n , и метод значительно эффективнее.

Главное преимущество инкрементального подхода проявляется при динамическом обновлении множества узлов. Если в уже построенное Парето-множество P добавляется один новый узел (например, после обновления загрузки узла), стоимость обновления составляет O (| P | • m ), а не O ( n ² • m ). В задаче предсказательного распределения ресурсов это особенно актуально: при поступлении новой задачи Z изменяется загрузка одного узла (того, на который была назначена предыдущая задача), и Парето-множество требует лишь локального обновления.

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

Экспериментальное исследование

Для экспериментального подтверждения теоретических оценок вычислительной сложности и сравнения рассматриваемых алгоритмов была разработана программа моделирования на языке Python. Эксперименты проводились на вычислительной платформе со следующими характеристиками: процессор Ryzen 5 5600, ОЗУ 32 Gb, Windows 11.

Генерация тестовых данных осуществлялась следующим образом. Для каждого эксперимента формировалось множество узлов U размером n , для каждого узла uⱼ случайным образом генерировался кортеж критериев C ( uⱼ ) = ⟨ c ₁, c ₂, c ₃⟩. Значения каждого критерия выбирались из логнормального распределения на отрезке [ c min , c max ].

Измерялось время выполнения каждого алгоритма в миллисекундах. Для устранения случайных флуктуаций каждый эксперимент повторялся R = 30 раз, после чего вычислялось среднее значение времени выполнения. Корректность всех алгоритмов проверялась сравнением возвращаемого ими множества P с эталонным результатом базового алгоритма.

Сравнение алгоритмов в зависимости от числа узлов n

В первой серии экспериментов исследовалось поведение алгоритмов от числа узлов-кандидатов n при фиксированном k = 3 и параметре фильтрации θ = 3.0. Значение n варьировалось в диапазоне от 10 до 1000.

Результаты первой серии экспериментов представлены на рис. 2 и 3, где показана зависимость среднего времени выполнения и среднего количества операций алгоритмов

Как видно из рисунка 2, все четыре алгоритма демонстрируют квадратичный рост времени выполнения при увеличении n , что соответствует теоретическим оценкам O( n ² · m ). Однако абсолютные значения времени и темп роста существенно различаются.

а)

б)

Рис. 3. Среднее количество операций при k = 3, а) график со всеми алгоритмами, б) график без предварительной фильтрации и базового алгоритмов

Результаты эксперимента демонстрируют следующее. Базовый алгоритм показывает выраженный квадратичный рост времени выполнения: от 0.05 мс при n = 10 до 21.79 мс при n = 1000, что соответствует теоретической оценке O ( n ² · k ).

Метод ранней остановки обеспечивает стабильное ускорение относительно базового на всем исследованном диапазоне – в среднем в 1.84× с незначительными отклонениями от точки к точке. При n = 1000 время выполнения составляет 13.58 мс. Стабильность ускорения обусловлена тем, что при логнормальном распределении значений критериев ожидаемое число проверяемых критериев до досрочного завершения остается постоянным и не зависит от n .

Инкрементальный алгоритм демонстрирует наибольшее ускорение среди рассматриваемых подходов и, в отличие от метода ранней остановки, это преимущество возрастает с увеличением n : от ×1.4–1.8 при малых n до ×2.9–3.9 при n ≥ 900. При n = 1000 время выполнения составляет 7.58 мс – более чем в 2.9 раза быстрее базового. Рост ускорения объясняется тем, что с увеличением n размер Парето-множества | P | растет медленнее, чем n , что снижает среднее число сравнений на каждом шаге инкрементального добавления.

Метод предварительной фильтрации в данном эксперименте не обеспечивает за- метного ускорения: среднее ускорение составляет лишь ×1.07, а в ряде точек метод незначительно уступает базовому алгоритму по времени. Причина состоит в характере ге- нерируемых данных: первый критерий c₁ имеет логнормальное распределение с выраженной правосторонней асимметрией, поэтому при θ = 3.0 порог фильтрации захватывает значительную часть узлов, и размер отфильтрованного множества U* лишь незна- чительно меньше исходного, 90–97% от U (рис. 4).

Рис. 4. Зависимость полноты Парето-множества от количества узлов

Таким образом, в условиях логнормального распределения критериев и при θ = 3.0 наиболее эффективным методом является инкрементальный алгоритм, обеспечивающий ускорение до ×3.9 без потери полноты P . Метод ранней остановки гарантирует стабильное двукратное ускорение при 100% полноте и применим без каких-либо ограничений на характер данных. Метод предварительной фильтрации требует тщательной настройки параметра θ с учетом распределения значений ключевого критерия – при неудачном выборе θ он не дает преимущества ни по скорости, ни по полноте.

Сравнение алгоритмов в зависимости от числа критериев k

Во второй серии экспериментов исследовалась зависимость времени выполнения от числа критериев k при фиксированном n = 200. Значение k варьировалось от 2 до 10. Результаты экспериментов продемонстрированы на рис. 5.

Рис. 5. Среднее время выполнения алгоритмов (мс) при n = 200

При увеличении числа критериев k наиболее эффективным методом становится ранняя остановка, преимущество которой монотонно возрастает. Инкрементальный метод целесообразно применять при малых k ( k < 4), причина состоит в том, что с увеличением k размер Парето-множества | P | растет - при большем числе критериев доминирование устанавливается реже, и в Парето-фронт попадает большая доля узлов. Это увеличивает число сравнений при каждом инкрементальном шаге, сильно снижая преимущество метода.

Влияние параметра θ на эффективность фильтрации

В третьей серии экспериментов исследовалось влияние порогового параметра 0 на эффективность метода предварительной фильтрации. Фиксировались n = 500, k = 3; параметр в варьировался от 1.0 до 5.0 с шагом 0.1.

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

Рис. 6. Влияние параметра θ на эффективность алгоритма фильтрации

При в = 1.0 метод обеспечивает максимальное ускорение по числу операций (х1497 относительно базового), однако полнота P составляет лишь 1.8% - подавляющее большинство Парето-оптимальных узлов отсекается. С увеличением в размер отфильтрованного подмножества U * и число операций монотонно возрастают, а полнота в целом улучшается, хотя и с заметными флуктуациями, обусловленными случайным характером генерируемых данных.

Можно выделить три характерных диапазона в . При в £ [1.0, 2.0] полнота остается низкой (до 76%), ускорение высокое (от х6 до ^х1497), однако результат нельзя считать практически применимым из-за значительных потерь Парето-оптимальных решений.

При 0 £ [2.0, 3.3] полнота достигает приемлемого уровня: значение 90% впервые достигается при 0 = 2.7, а 97% - при 0 = 3.1, при этом ускорение по операциям составляет ^х2.2 и х1.2 соответственно. Начиная с 0 = 3.4 полнота стабилизируется на уровне 100% -фильтр перестает отсекать какие-либо Парето-оптимальные узлы. При 0 > 3.5 в отфильтрованное множество попадают все 500 узлов, и метод вырождается в базовый алгоритм, не давая никакого преимущества.

Таким образом, выбор параметра 0 определяет баланс между точностью и эффективностью. Эта дилемма - "точность против эффективности" - является общей для многих методов аппроксимации в многокритериальной оптимизации. Детальный обзор таких подходов представлен в работе [14].

Заключение

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

По результатам работы сформулированы следующие выводы:

• 1.    Установлено, что базовый алгоритм полного попарного сравнения имеет вычислительную сложность O ( n ² • k ), что при большом числе узлов-кандидатов и высокой интенсивности входящего потока задач может стать доминирующей составляющей нагрузки планировщика. Введено условие применимости базового алгоритма в системе реального времени через параметр загрузки L < 1.

• 2.    Рассмотрены три подхода снижения алгоритмической сложности. Метод предварительной фильтрации сокращает размер множества кандидатов до начала попарного сравнения, достигая ускорения порядка 1/α² при коэффициенте сохранения α, однако сопряжен с возможными потерями полноты Парето-множества. Метод ранней остановки не изменяет результат алгоритма, снижая среднее число проверяемых критериев до ~2 при любом k . Инкрементальный метод обеспечивает ускорение при динамическом обновлении множества узлов, сводя стоимость локального обновления к O (| P | • k ).

• 3.    Экспериментально подтверждено, что при увеличении числа узлов n наибольшее и возрастающее ускорение обеспечивает инкрементальный алгоритм при гарантированной полноте P . При увеличении числа критериев k наиболее эффективной оказывается ранняя остановка, ускорение которой монотонно возрастает. Инкрементальный метод предпочтителен при малых k , когда размер Парето-фронта невелик.

• 4.    Для метода предварительной фильтрации экспериментально определен практически целесообразный диапазон порогового параметра для заданной конфигурации имитационной модели, при котором полнота Парето-множества составляет не менее 90% при сохранении умеренного ускорения. При 0 > 3.5 метод вырождается в базовый алгоритм, не давая никакого преимущества.

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

Направлениями дальнейших исследований являются: анализ вычислительной сложности при использовании комбинаций рассмотренных методов; исследование поведения алгоритмов при числе критериев k > 10 и большом числе Парето-оптимальных решений; экспериментальная проверка на реальных данных о загрузке вычислительных кластеров. Также перспективным направлением является комбинирование разработанных методов с современными алгоритмами недоминируемой сортировки, например, с SETNDS [15], что может дополнительно повлиять на производительность.