Введение. 
Роевой алгоритм планирования работы многопроцессорных вычислительных систем

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

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

Российские и зарубежные ученые разработали большое число алгоритмов и методов решения распределительных задач различающихся как эффективностью, так и областью применения. Поскольку РЗ принадлежат к классу NP-полных задач, разработка эффективных алгоритмов их решения по прежнему остается актуальной проблемой теории расписаний. Разработанные методы решения распределительной задачи принято разделять на два больших класса: точные и приближенные. Среди существующих известных и эффективных точных методов решения РЗ наибольшее распространение получили алгоритмы, построенные по схеме метода ветвей и границ (МВГ) [3]. Существенным недостатком метода ветвей и границ является экспоненциальное увеличение сложности решения относительно размерности РЗ. В ряде работ [4] предлагаются подходы, позволяющие сократить комбинационную сложность алгоритмов, построенных по схеме метода ветвей и границ [2]. Особенностью метода ветвей и границ является то, что всегда существует вероятность полного перебора и необходимы достаточно большие временные затраты, особенно при решении задач повышенной размерности.

В связи с этим широкое распространение получили приближенные методы, ориентированные на получение некоторого приемлемого или допустимого решения [5;6]. Достоинство таких методов состоит в высокой скорости решения, характеризующиеся полиномиальной или, даже, линейной зависимостью от размерности задачи. К числу недостатков следует отнести невысокую точность методов данного класса. К числу наиболее распространенных приближенных методов относятся так называемые списочные и эвристические методы. Обладая в основном, линейной сложностью решения относительно размерности задачи, списочные методы крайне эффективны с точки зрения времени решения РЗ. С другой стороны, отклонение получаемых решений от оптимального значения может достигать 30%, что часто не удовлетворяет предъявляемым требованиям к решениям. Высокая трудоемкость точных методов и низкая эффективность приближенных списочных методов резко снизили их практическое применение. В связи с этим большая часть разработок была направлена на применение эвристических подходов. Анализ существующих алгоритмов (последовательных, итерационных и т. д.), приведенный в [5−7] показывает, что для разработки более эффективного алгоритма, который отвечает предъявляемым современным требованиям, необходимы новые технологии и подходы. В последние годы интенсивно разрабатывается научное направление, объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений [8,9]. Одним из таких направлений являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта [10−13].

Такие методы являются итеративными, эвристическими методами случайного поиска. Особенно наблюдается стремительный рост интереса к разработке алгоритмов, инспирированных природными системами. Среди них активно рaзвивaются методы роевого интеллекта (Swarm Intelligence) [8−10], в которых совокупность простых агентов конструирует стратегию своего поведения без наличия глобального управления. Одним из новейших мультиагентных методов интеллектуальной оптимизации является метод муравьиной колонии [9]. В работе излагается метод планирования комплекса программ в многопроцессорных вычислительных системах, базирующийся на моделировании адаптивного поведения муравьиной колонии.