Software & Systems

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

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

Самыми известными и наиболее эффективными из методов точного решения распределительной задачи являются алгоритмы, в основе которых лежат принципы метода ветвей и границ [2–4]. Однако следует отметить, что эти алгоритмы имеют свойство экспоненциального роста сложности искомого решения относительно размерности распределительной задачи. Это особенно заметно, когда распределяемые в задаче задания характеризуются небольшой вариацией значений их размеров. Основные два дефекта, которые часто возникают в алгоритмах на основе метода ветвей и границ, указаны в работе [4]. В ней предлагается модификация, которая может уменьшить комбинационную сложность алгоритма, предложенного Романовским [2]. Главная особенность метода ветвей и границ состоит в том, что обязательно возникнет такой пример, при решении которого необходим полный перебор. Поэтому для задач повышенной размерности возникнут большие временные затраты, хотя комбинаторная сложность уменьшится.

Алгоритмы приближенного поиска не могут гарантированно найти при решении распределительной задачи глобальный оптимум. Они позволяют получать некоторое допустимое или приемлемое решение [4–6]. Точность алгоритмов этого класса невысока, но основное достоинство заключается в высокой скорости получения решения, которая имеет полиномиальную, а иногда даже линейную зависимость от заданного порядка задачи. Наибольшее распространение в классе приближенных алгоритмов получили списочные и эвристические методы. В основном списочные методы имеют линейную сложность решения (относительно размерности задачи). В связи с этим, с точки зрения времени построения расписаний, они обладают большой эффективностью. К сожалению, при получении решений погрешность может достичь 30 %, что неприемлемо к заданным практическим требованиям. Интерес к использованию эвристических подходов возник в связи с низкой точностью приближенных списочных алгоритмов и высокими вычислительными требованиями точных методов.

В литературе [5–11] приведены разработанные ранее алгоритмы (последовательные, итерационные и т.д.). Их обзор, сравнение и анализ показали, что для разработки более эффективного алгоритма требуются новые технологии и подходы. Возможности применения генетического алгоритма для решения однородной распределительной задачи рассматриваются в [12, 13]. Как показывают исследования, алгоритм лучше срабатывает при значительном увеличении популяции и числа итераций. В [14] приведены некоторые возможные модификации использования алгоритма поиска Табу. Эксперименты показывают, что этот алгоритм не всегда способен дать оптимальные решения. Качество решений возрастает в том случае, если его использовать совместно с алгоритмом случайного поиска. В [15] авторами было проведено исследование возможности использования нейронных сетей для решения однородной распределительной задачи и приведены результаты поставленных экспериментов. Предлагается использовать динамическую нейронную сеть, основанную на нейронах непрерывного и двоичного типов. Из результатов экспериментальных исследований следует, что метод позволяет получать решения, результаты которых могут быть улучшены.

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

В настоящее время наиболее перспективным является интенсивно разрабатываемое в последние годы научное направление, объединяющее различные математические методы, в которых принятие решений осуществляется на основе принципов, содержащих природные механизмы [15–21]. Эти методы являются итерационными, эвристическими методами случайного поиска. Наиболее активно развиваются методы роевого интеллекта (Swarm­Intelligence) [17–21]. В них совокупность простых агентов конструирует стратегию своего поведения без глобального управления.

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

Постановка однородной распределительной задачи теории расписаний

Пусть исполнительная система состоит из n идентичных, параллельно работающих исполнителей E={ei|i=1, 2, …, n}. На вход системы поступает множество m независимых заданий (работ) W={wj| j=1, 2, …, m}, которые необходимо распределить между исполнителями. Известна стоимость (ресурс выполнения) каждого j-го задания rj, и она одинакова для любого i-го исполнителя ei. Таким образом, множеству W сопоставлено множество стоимостей: R={rj| j=1, …, m}. l-м решением однородной распределительной задачи является множество Vl={Wli|i=1, 2, …, n}, в котором подмножества заданий Wli отвечают обязательному свойству:

("i, j) [((i¹j)&(WliÎVl)&(WljÎVl))→

→ ((WliÇWlj =Æ)&(ÈWli = W))].                     (1)

Запланированная вариантом решения Vl загрузка заданиями каждого исполнителя ei оценивается ресурсом:

=,                                                            (2)

где rk |wkÎWli.

В качестве оценки решения Vl рассматривается величина

Fl=max(Rli).                                                         (3)

Наиболее распространенным критерием оптимизации однородной распределительной задачи является минимаксный критерий

F= min Fl = minmax (Rli).                                 (4)

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

Представим решение распределительной задачи в виде двудольного графа: Hl=(EÈW, Ul), где E={ei| i=1, 2, …, n} – множество вершин (первая доля), соответствующих множеству исполнителей, а W={wj|j=1, 2, …, m} – множество вершин (вторая доля), соответствующих множеству заданий (ра- бот); Ul – множество ребер, связывающих вершины множества E с вершинами множества W. Для наглядности представления конкретного решения Vl сгруппируем множество заданий W в подмножества (рис. 1).

Пусть Uli – множество ребер двудольного графа Hl, связывающих вершину ei с вершинами множества Wli, ÈUli=Ul. Отличительной особенностью представленного двудольного графа Hl=(EÈW, Ul) является то, что число ребер множества Uli равно числу вершин множества Wli. Каждое ребро uzÎUli, с одной стороны, инцидентно вершине ei, а с другой – инцидентно только одной вершине wkÎWli. Назовем двудольный граф, представляющий решение Vl, графом-решением Hl. Отметим, что локальная степень любой вершины wjÎW равна единице, а локальная степень вершины ei равна мощности множества Wli, то есть ρ(wj) = 1, ρ(ei) = |Wli|.

В работе поиск решения Vl сводится к поиску на полном двудольном графе Hnm такого графа-решения Hl, для которого оценка Fl имеет минимальное значение.

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

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

Рассмотрим принципы решения однородной распределительной задачи методами муравьиной колонии. Поиск решений осуществляется на полном двудольном графе. Как указывалось выше, базовый метод заключается в реализации итерационной процедуры поиска лучшего решения. Работа поисковой процедуры начинается с построения в соответствии со спецификой решаемой задачи графа поиска решений. Для поиска решений формируется полный двудольный граф Hnm = = (EÈW, U). В графе Hnm каждая вершина ei связана со всеми вершинами множества W, а каждая вершина wj связана со всеми вершинами множества E, то есть ρ(wj) = |U|, ρ(ei) = |W|, |U| = nm. Задается размер популяции искусственных муравьев. За каждым муравьем закрепляется стартовая вершина. В качестве стартовых вершин рассматриваются вершины wjÎW.

Моделирование поведения муравьев связано с распределением феромона на ребрах графа Hnm. На начальном этапе на всех ребрах U графа Hnm откладывается одинаковое (небольшое) количество феромона Q/v, где v = |U|. Параметр Q задается априори. Будем обозначать граф Hnm после отложения на нем на итерации t феромона как Hnm(t). После начального отложения – Hnm(0). Процесс поиска решений итерационный. Каждая итерация t включает три этапа. На первом этапе каждой итерации t выполняются процедуры муравьиного алгоритма. Каждый l-й агент формирует на ребрах графа Hnm(t–1) свой собственный граф-решение Hl(t), определяется решение Vl(t), соответствующее гра­фу-решению Hl(t), и оценка решения Fl(t).

На втором этапе итерации t каждый муравей откладывает феромон на ребрах графа Hnm(t–1), соответствующих ребрам построенного графа-решения Hl(t).

Количество феромона Dτl(t), откладываемое муравьем al на каждом ребре построенного графа-решения Hl(t), определяется следующим образом: Dτl(t) = Q / Fl(t), где t – номер итерации; Q – общее количество феромона, откладываемое муравьем на ребрах графа-решения Hl(t); Fl(t) – целевая функция для решения, полученного муравьем al на t-й итерации. Чем меньше Fl(t), тем больше феромона откладывается на ребрах построенного графа-решения Hl(t) и, следовательно, тем больше вероятность выбора этих ребер при построении графа-решения на следующей итерации.

Обозначим fij(t) суммарное количество феромона, скопившееся на ребре uk двудольного графа Hnm(t), связывающего вершину ei с вершиной wj после выполнения второго этапа итерации t.

После того как каждый агент сформировал решение и отложил феромон, на третьем этапе итерации t происходит общее испарение феромона на ребрах двудольного графа Hnm(t) в соответствии с формулой fij(t) = fij(t)(1– ρ), где ρ – коэффициент обновления.

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

Рассмотрим теперь конструктивный алгоритм построения муравьем двудольного графа-решения Hl(t) на полном двудольном графе Hnm(t–1).

Последовательно (или случайным образом) выбираются вершины wjÎW двудольного графа Hnm(t–1), начиная с первой (стартовой). Для выбранной вершины wj определяется набор ребер Uj(t), связывающих wj со всеми вершинами ei множества E. Для каждого ребра ukÎUj(t), связывающего вершину ei с вершиной wj, определяется параметр fij – суммарный уровень феромона на этом ребре.

Вероятность Pk включения ребра ukÎUj(t) в формируемый граф-решение Hl(t) определяется соотношением Pk = fij/∑i(fij).

Агент с вероятностью Pk выбирает одно из ребер, которое включается в формируемый граф-решение Hl(t).

Временная сложность этого алгоритма зависит от времени жизни колонии t (число итераций), количества исполнителей n и числа работ m и определяется как O(l∙c2∙m). Далее приведены алгоритм поведения муравьиной колонии и алгоритм муравья.

Алгоритм поведения муравьиной колонии.

1. Задаются число исполнителей – n, число работ – m, начальное количество феромона – Q.

2. Строится полный двудольный граф Hnm(0) = = (EÈW, U(0)), на ребрах которого отложено начальное количество феромона.

3. За каждым муравьем al закрепляется стартовая вершина wlÎW.

4. Задаются число итераций – NT, число муравьев, формирующих независимо друг от друга решения на одной итерации, – NR.

5. t=1 (t – номер итерации).

6. l=1 (l – номер агента).

7. (Алгоритм муравья). Муравей al строит на полном двудольном графе Hnm(t–1)=(EÈW, U(t–1)) двудольный граф-решение Hl(t).

8. Рассчитывается оценка Fl(t) построенного двудольного графа-решения Hl(t).

9. Если l

10. l=1.

11. Муравей al откладывает на ребрах полного двудольного графа Hnm(t–1), соответствующих ребрам построенного двудольного графа-решения Hl(t), феромон в количестве Dτl(t) = Q / Fl(t).

12. Если l

13. На третьем этапе итерации t происходит общее испарение феромона на всех ребрах двудольного графа Hnm(t) в соответствии с формулой fij = fij(1 – ρ), где ρ – коэффициент обновления.

14. Находится агент с лучшим решением F(t), полученным после выполнения t итераций, которое запоминается.

15. Если t

16. Конец работы алгоритма.

Рассмотрим теперь конструктивный алгоритм построения муравьем двудольного графа-решения Hl(t) на полном двудольном графе Hnm(t–1).

Алгоритм муравья.

1. s=0 (s – индекс списка вершин W(s), указывающий на число удаленных вершин из исходного списка W).

2. Формируется исходный список вершин W(s)= = {wj| j=1, 2, …, m}, включающий все вершины множества W, то есть W(s)= W={wj| j=1, 2, …, m}.

3. В списке W(s) выбирается вершина wj, которая закреплена за муравьем al, и удаляется из списка. Переход к пункту 5.

4. Случайным образом в списке W(s) выбирается вершина wj, которая удаляется из списка.

5. s = s+1, wjÎW.

6. Для выбранной вершины wj определяется набор ребер Uj, связывающий wj со всеми вершинами ei множества E, |Uj|=n.

7. Для каждого ребра ukÎUj, связывающего вершину ei с вершиной wj, определяется параметр fij – суммарный уровень феромона на этом ребре.

8. Для каждого ребра ukÎUj по формуле Pk = =fij / ∑i(fij) рассчитывается вероятность включения ребра ukÎUj в формируемый граф-решение Hl.

9. Агент с вероятностью Pk выбирает одно из ребер, которое включается в формируемый граф-решение Hl(t).

10. Если s

11. Двудольный граф-решение Hl(t) полностью сформирован. Конец работы алгоритма муравья.

Разработка программы

Алгоритм решения задачи распределения работы программ на многопроцессорных системах был запрограммирован на языке c# на платформе Windows. При этом все исследования проводились на компьютере типа Intel® Core™ i5 CPU 3.33 GHz и ОЗУ размером 4 Гб.

Язык c# был выбран по нескольким причинам. Во-первых, он позволяет быстро наладить разработку на начальных этапах, что дает возможность в короткие сроки спроектировать программный продукт, который потом можно будет отлаживать с помощью средств Visual Studio.

Огромное количество библиотек с .NET идет в базе, плюс к ним множество свободно доступных библиотек, что покрывает практически все первостепенные задачи разработки под Windows. Наличие большого количества стандартных типов почти избавляет от библиотек, где базовые типы переопределены. В силу того, что библиотеки С# сравнительно молодые, интерфейсы библиотек, как правило, лучше вписываются в те или иные шаблоны проектирования.

В Visual Studio есть возможность подключения системы контроля версий и работы с ней. Эта особенность сильно помогает в процессе коллективной разработки.

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

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

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

BaseDisplayer – класс, содержащий в себе виртуальные функции, предназначенные для отрисовки различных статистических элементов на формах (графиках и т.д.). От него наследуются классы DrawBestSolution, ProblemDisplayer, RAlgo­rithmDisplayer. DrawBestSolutions предназначен для отрисовки графика нахождения лучших решений по итерациям; ProblemDisplayer – для отображения текущей решаемой задачи на форме, предоставляющей возможность подгрузки решения из файла; RAlgorithmDisplayer – для отображения информации о текущих настройках алгоритма.

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

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

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

На рисунке 2 приведена структурная схема программы, описывающая компонентное устройство программы.

Класс RDistributionAlgorithm определяет переписанные функции самого муравьиного алгоритма и представляет основную программную логику его работы.

Класс BaseProblem содержит некоторые базовые данные о проблеме, решение которой происходит на момент работы алгоритма. Он верхний в иерархии наследования.

Класс RproblemData содержит все необходимые исходные данные для работы алгоритма.

Класс RdistributionAlgorithm наследуется от RproblemData. Это сделано для более упрощенного доступа ко всем исходным данным. Класс содержит реализацию всех механизмов, необходимых для работы алгоритма моделирования поведения колонии муравьев.

Класс BaseFormReader. Базовый класс, предназначенный для считывания информации об исходных данных с формы. Содержит только виртуальные функции.

Класс ProblemConfugurer. Конфигуратор исходных данных. Наследуется от BaseFormReader. Также имеет доступ к RdistributionProblem. Преобразует исходные данные задачи в формат, использующийся внутри программы.

Класс BaseLoader предназначен для загрузки файлов. Содержит только виртуальные функции.

Класс RdistributionLoader. Предназначен для загрузки данных с привязкой к задаче распределения программ в многопроцессорных системах. Реализует возможность подгрузки файлов из формата .xml или сериализованного бинарного файла.

Класс BaseSolution. Представляет базовое построенное решение задачи внутри программы. Содержит только виртуальные функции.

Класс RdistributionSolution. Содержит информацию о полученном решении с привязкой к задаче распределения программ в многопроцессорных системах. Наследуется от BaseSolution.

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

Программная реализация алгоритма

Рассмотрим реализацию алгоритма моделирования поведения колонии муравьев (рис. 3).

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

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

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

Если все агенты на текущей итерации выполнили построение решений, производится изменение множества альтернатив. При этом каждое решение сравнивается с найденным лучшим решением на данной итерации. Чем хуже решение, тем меньшее количество феромона откладывает агент, который данное решение получил. Откладывание феромона в матрицу альтернатив осуществляется по формуле Pdi = , i = {0, 1, …, n}, где Pd – количество откладываемого феромона муравьем на i-й итерации; Sb – оценка лучшего найденного решения; Sc – оценка текущего найденного решения.

Проведение экспериментальных исследований

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

Для этого была применена процедура формирования контрольных тестовых примеров с уже известными результатами (оптимумом).

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

Для получения достоверных выводов была проведена серия тестов-экспериментов. Временная зависимость разработанного алгоритма определяется временем жизни колонии t (количество генераций), числом исполнителей n и числом работ m и определяется как O(t∙n2∙m). Тестирование показало, что в 97 % случаев сформированное пространство решений содержит глобальное оптимальное решение.

Тестирование, определяющее сходимость алгоритма, выполнялось следующим образом. Для каждого теста запоминался номер итерации, после которой улучшения оценки не происходило. Проводилась серия из 50 тестов, в которой находились минимальный и максимальный номера итерации. Также выполнялся расчет среднего значения количества итераций, улучшения оценки после которых не происходило. Фактически в каждой серии тестов определялось лучшее решение, которое являлось оптимальным. Тестовые эксперименты показали, что схождение алгоритма происходит на 120-й генерации при объеме популяции М = 90.

Сравнение значений критерия, полученных муравьиным алгоритмом на бенчмарках, у которых оптимум уже известен, показало, что у 80 % тестов полученный результат был оптимальным, у 15 % тестов результаты были на 3 % хуже оптимального, а у 5 % тестов результаты были хуже не более, чем на 2 %. На основании проведенных экспериментальных исследований можно сделать вывод, что разработанный алгоритм позволяет получить результаты на 2–3 % лучше тех, что получены имеющимися алгоритмами [2–10].

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

Для сравнения эффективности были выбраны генетический алгоритм, селективно-перестановочный алгоритм (СПА) [4, 6–10], алгоритм различных наборов работ и машин (DJMS) [22], алгоритм моделирования поведения колонии муравьев (ACO).

Эти алгоритмы были выбраны в силу перспективности и хороших результатов, показанных ими при проведении экспериментов [4, 6–10].

Сравнивался алгоритм адаптивного поведения муравьиной колонии с различными алгоритмами решения однородной распределительной задачи. В качестве оптимальных настроек для алгоритма моделирования поведения колонии муравьев использовались следующие параметры: Nc = 50 – размерность колонии, Ni = 100 – количество итераций для каждого эксперимента. Работа алгоритма была смоделирована без учета элитных особей. Подобные параметры также использовались для алгоритма селективных перестановок.

Каждый проведенный эксперимент содержал три параметра: m – количество работников, n – количество работ, U – интервал работ, использующийся для генерации списка работ на каждой ите- рации. Для каждого набора работ использовались 100 задач. Суммарно для сравнения методов ACO и DJMS было проанализировано 1 900 решений.

Для оценки решений использовалась нижняя граница (Lower bound):

Сравним эффективность метода моделирования поведения адаптивной колонии с эффективностью методов DJMS и LPT (табл. 1). Результаты экспериментов метода DJMS взяты из [22]. Для каждого метода в каждой строчке таблицы показано количество оптимальных решений из проведенных 100 экспериментов.

Таблица 1

Сравнение эффективности методов

Table 1

Method effectiveness comparison

Из таблицы 1 видно, что алгоритм DJMS опережает стандартный LPT. Стоит отметить, что этот алгоритм использует связку концепций LPT и MF. Очевидно, что такая связка дает более хороший результат. В свою очередь, алгоритм ACO опережает DJMS, что обусловлено использованием вероят- ностного подхода и выцветанием отдельных альтернативных выборов решений.

Сравним алгоритмы АСО и СПА.

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

Таблица 2 позволяет сравнить алгоритмы СПА и АСО. В данном случае применялся алгоритм селективных перестановок, использующий одинарные перестановки. Данные для СПА взяты из [23].

Таблица 2

Сравнение СПА и АСО

Table 2

Comparison of selective-permutation algorithm and АСО

Алгоритм муравьиной колонии показал эффективность 98,6 %, в то время как эффективность алгоритма ListScheduling составила 21,9 %, Thre­sholdHeuristic – 79,1 % и Scattersearch – 97,7 % (результаты были взяты из [24]).

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

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

Методы СПА и ACO показывают приблизительно равные результаты с преимуществом метода ACO около 2,5 %. Также стоит отметить, что метод ACO показывает более хороший результат на большом диапазоне работ. В целом данный метод имеет преимущество.

Заключение

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

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

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

Работа выполнена при финансовой поддержке РФФИ, грант № 17-07-00997.

Литература

1.     Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: Изд-во МГУ, 2011. 188 с.

2.     Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети. СПб: Энергоатомиздат, 1987. 329 с.

3.     Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 156 с.

4.     Нейдорф Р.А., Жикулин А.А. Быстродействующая модификация алгоритма оптимизации решения // AIS-IT’14: тр. Конгресса по интеллект. сист. и информ. технол. В 4-х т. М.: Физматлит, 2010. Т. 1. C. 15–22.

5.     Кобак В.Г., Будиловский Д.М. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов // Вестн. Донск. гос. техн. ун-та. 2006. № 4. С. 327–334.

6.     Нейдорф Р.А., Жикулин А.А. Исследование вариантов модификации приближенных алгоритмов решения однородных распределительных задач, повышающих их эффективность // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): тр. X Междунар. науч.-техн. форума. Ростов н/Д: Изд-во ДГТУ, 2012. С. 370–375.

7.     Нейдорф Р.А., Жикулин А.А. Селективно-перестановочный метод приближенного решения однородной распределительной задачи. Комбинационные перестановки // Изв. ЮФУ. Сер. Технич. науки. 2013. № 7. С. 167–172.

8.     Кобак В.Г. Эффективные методы решения однородных распределительных задач на основе минимаксного критерия. Ростов н/Д: Изд-во ДГТУ, 2013. 99 с.

9.     Титов Д.В. Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах: дисс. ... канд. технич. наук. Ростов н/Д: Изд-во ДГТУ, 2010. 179 с.

10.   Жикулин А.А. Методы высокоэффективной ресурсной модификации алгоритма Романовского для решения однородных распределительных задач. дисс. ... канд. технич. наук. Ростов н/Д: Изд-во ДГТУ, 2014. 156 с.

11.   Davidović T., Šelmić M., Teodorović D., Ramljak D. Bee colony optimization for scheduling independent tasks to identical processors. Jour. of Heuristics 2012, vol. 18, iss. 4, pp. 549–569.

12.   Demirel T., Özkır V., Demirel N.Ç., Taşdelen B. A Genetic Algorithm approach for minimizing total tardiness in parallel machine scheduling problems. Proc. World Congress on Engineering, 2011, vol. II, pp. 267–281.

13.   Raghavendra1 B.V., Murthy A.N. Workload balancing in identical parallel machine scheduling while planning in flexible manufacturing system using genetic algorithm. ARPN Jour. of Engineering and Applied Sciences, 2011, vol. 6, pp. 113–126.

14.   Aslam M.U., Nasr M.M., Al-Harkan I.M. Scheduling of jobs on identical parallel machines to minimize total flow time subject to optimal makespan. Applied Mechanics and Materials, 2014, vol. 529, pp. 390–395.

15.   Akyol D.E. Identical parallel machine scheduling with dynamical networks using time-varying penalty parameters. Multiprocessor Scheduling, Theory and Applications, I-Tech Education and Publishing, 2007, pp. 293–315.

16.   Dorigo M. and Stützle T. Ant colony optimization. MIT Press, Cambridge, MA, 2004, 234 p.

17.   Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования: монография. Таганрог: Изд-во ЮФУ, 2013. 199 с.

18.   Raidl G.R. A unified view on hybrid metaheuristics. LNCS. Springer-Verlag, 2006, рр. 1–12.

19.   Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Изв. ЮФУ. 2012. № 7. С. 27–35.

20.   Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Изв. ЮФУ. 2013. № 7. С. 41–47.

21.   Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адаптивного поведения биологических систем // Нейрокомпьютеры: разработка, применение. 2010. № 2. С. 28–34.

22.   Лебедев Б.К., Лебедев О.Б., Нацкевич А.Н. Решение однородной распределительной задачи методом моделирования адаптивного поведения колонии муравьев. Свид. о гос. регистр. прогр. для ЭВМ № 2017611229 от 27.01.2017.

23.   A new algorithm to minimize makespan on identical parallel machines. URL: http://www.pomsmeetings.org/confpapers/ 025/025-0543.pdf (дата обращения: 09.04.2017).

24.   Iori M., Martello S. Scatter search algorithms for identical parallel machine scheduling problems. URL: http://www.springer. com/cda/content/document/cda_downloaddocument/9783540789840-c1.pdf?SGWID=0-0-45-552307-p173814816 (дата обращения: 09.04.2017).