автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Алгоритмы локального поиска для задачи календарного планирования с ограниченными ресурсами

На правах рукописи

СТОЛЯР Артем Александрович

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

специальность 05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени

Новосибирск - 2005

Работа выполнена в Институте математики им. С.Л. Соболева СО РАН

Научные руководители:

Официальные оппоненты:

Ведущая организация

доктор физико-математических паук, профессор Берсенев Владимир Леонидович, кандидат физико-математических паук, доцент Кочетов Юрий Андреевич. доктор технических наук, профессор Павлов Виктор Николаевич, кандидат экономических паук, доцент Ляхов Олег Алексеевич. Вычислительный центр РАН.

Защита состоится 29 июня 2005 г. в 15 часов па заседании диссертационного совета Д.003.061.02 в Институте вычислительной математики и математической геофизики СО РАН по адресу: пр. Академика Лаврентьева, 6, 630090, г. Новосибирск.

С диссертацией можно ознакомиться в библиотеке Института вычислительной математики и математической геофизики СО РАН.

Автореферат разослан 29 мая 2005 г.

Ученый секретарь диссертационного совета Д.003.061.02 при Институте вычислительной математики и математической геофизики СО РАН доктор физико-математических паук

Сорокин СБ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Исследования задач календарного планирования проводятся уже более 40 лет. Актуальность этих исследований обусловлена важными практическими приложениями. С математической точки зрения исследуемые задачи относятся к числу NP-трудпых1 задач дискретной оптимизации. Для их решения разрабатывались как точные методы, в большинстве своем основанные на схеме ветвей и границ, так и приближенные детерминированные и вероятностные методы. Часть работ посвящена также выявлению полиномиально разрешимых подклассов задач.

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

Известно2, что для любого е > 0 существование полиномиального приближенного алгоритма с гарантированной оценкой n~£ относительного уклонения от оптимума влечет NP=ZPP. Данное обстоятельство вызывает особый интерес к приближенным методам, среди которых следует отметить жадные алгоритмы, алгоритмы локального поиска, а также их вероятностные варианты.

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

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

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

1 Гэри М., Джонсон Д., Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982.

2 Mohring R. H., Schulz A. S., Stork F., Uetz M. Solving project scheduling problems by minimum cut computations // Manag. Sci. 2003. V. 49, N 3. P. 330 350.

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

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

Апробация работы. Основные результаты диссертации докладывались па Международной конференции "Дискретный анализ и исследование операций"(г. Новосибирск, 2000, 2002, 2004), на 12-й Международной Байкальской конференции (г. Иркутск, 2001), на Симпозиуме по исследованию операций (г. Дуйсбург, Германия, 2001), на конференции "Математическое программирование и приложения"(г. Екатеринбург, 2003), на Международной объединенной конференции по исследованию операций EURO/INFORMS (г. Стамбул, Турция, 2003), на 9-й международной конференции но задачам календарного планирования PMS'04 (г. Напси, Франция, 2004), на научных семинарах в Институте математики им. С.Л. Соболева СО РАН.

Публикации. По теме диссертации автором опубликовано двенадцать работ.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы из 109 наименований и приложения. Общий объем работы — 121 страница, включая 30 рисунков и 39 таблиц.

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

J Martello S., Toth P. Knapsack problems. Algorithms and computer implementations. Chichester: John Wiley & Sons, 1990.

4 Kolisch R., Schwindt C., Sprecher A. Benchmark instances for project scheduling problems // Project Scheduling. Recent Models, Algorithms and Applications. Boston: Ivluwer Acad. Publ., 1999. P. 197-212.

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

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

множество работ,

1Р] : множество непосредственных предшественников работы j 6 <7,

предполагается, что 0 6 Р] и ] Е Рп+1 Для всех j = 1,... ,п, К : множество типов ресурсов,

Як : объем ресурса А-го типа, выделяемый в каждый момент времени, гд. : объем ресурса к-го тина, необходимый для выполнения работы у в каждый момент времени, : длительность выполнения работы ].

Переменные задачи:

в] : момент начала работы j,

с,- = Sj + ф] : момент окончания работы ].

Через Т(8) = тахс, обозначим длину расписания 5 = {й./, j £ ■/}.

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

minT(S)

при ограничениях

где A(t) = {j G J I Sj < t < Cj} — множество работ, находящихся в процессе выполнения в момент времени t. Задача состоит в определении значений Sj,j £ J, удовлетворяющих условиям предшествования, ограничениям по ресурсам и минимизирующим время окончания всех работ. Целевая функция задаст время завершения проекта. Первое ограничение соответствует условиям предшествования, второе — выделяемым ресурсам.

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

В разделе 1.1 определяются три окрестности, используемые в схеме локального спуска. Все они определяются для так называемого активного расписания5, закодированного в виде упорядоченного списка работ L.

Первая окрестность, N\(S) основана на понятии критической Рассмотрим взвешенный ориентированный граф G = (V, Е) с множеством вершин V = J и множеством дуг Е, состоящим из пар (i,^ к и х , что сг = Sj в расписании S. Дуге (i,j) припишем вес иг^Порлу ченный граф является сетью. По построению все пути из источника в сток, соответствующий работе (п + 1), имеют одинаковую длину. Они называются критическими. Дугу называют критической, если она принадлежит некоторому критическому пути и пара (i,j) не связана условиями предшествования. Найдем в G критический путь СР с минимальным числом дуг. Идея построения окрестности N\(S) состоит в том, чтобы изменить список L, сделав хотя бы одну критическую дугу некритической для пути СР. Окрестность определяется с помощью трех операторов сдвига.

Мощность окрестности имеет порядок О(п).

Важным свойством любой окрестности является свойство оптимальной связности.

Определение 1 Графом соседства для окрестности N(S) называется такой граф G = (V, Е), в котором множество вершин есть множество допустимых решений задачи, а множество дуг — совокупность таких пар (Si, S2), для которых S2 € N(Si), S\,S2 £ V.

Определение 2 Окрестность N(S) будем называть оптимально связной, если в графе соседства существует путь из произвольной вершины в вершину, соответствующею оптимальному решению.

Теорема 1 Окрестность N\(S) не является оптимально связной.

5 Sprecher А., Kolisch R., Drexl A., Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem // European J. Oper. Res. 1995. V. 80. P. 94-102.

6 Daar Т., Brucker P., Knust S. Tabu-search algorithms for the resource-constrained project scheduling problem. Working Paper, Universität Osnabrück, 1997.

Окрестность N2(8), как и окрестность ,N\(S), определяется для активного расписания S и соответствующего списка L. Для каждой пары (i,j), не связанной условиями предшествования, соседний список L\ получается из списка L переносом работы г вместе со всеми се последователями, стоящими перед j в L, непосредственно за работу j. Основное отличие от предыдущей окрестности состоит в том, что пара (ij) не обязана соответствовать критической дуге и может не принадлежать Е. Окрестность N2(S) состоит из активных расписаний, получаемые из соседних списков. Она имеет мощность порядка

Теорема 2 Окрестность N2(8) является оптимально связной.

При определении окрестности Nz(S) используется приближенное решение вспомогательной задачи о многомерном рюкзаке. Для каждой работы j выделяется подмножество работ Bl(j), выполняемых в текущем расписании S параллельно, непосредственно до или после работы j. Для этих работ вычисляются новые значения переменных Sj. Затем полученное частичное расписание достраивается до полного, не меняя порядка выполнения оставшихся работ. Мощность окрестности — 0{п).

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

В разделе 1.2 приводится описание библиотеки тестовых задач PSPLib, созданной в 1996 году. Ее авторы — немецкие ученые R. Kolisch и A. Sprccher. Библиотека содержит широкий спектр примеров разной степени сложности как для рассматриваемой здесь модели, так и для многих других моделей календарного планирования. Библиотека имеет сайт в ИНТЕРНЕТ8, где размещаются файлы исходных данных в свободном доступе.

Помимо исходных данных, библиотека содержит оптимальные решения для примеров размерности п = 30. Для остальных примеров в пей содер-

7 Sprecher A., Kolisch R., Drexl A., Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem // European J. Oper. Res. 1995. V. 80. P. 94-102.

8 http://www.bwl.uni-kiel.de/Prod/psplib/index.html

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

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

Как отмечалось выше, тестовые примеры библиотеки PSPLib различаются числом работ, условиями предшествования и количественными характеристиками выделения и потребления ресурсов. Результаты показывают, что в данной библиотеке наибольшим числом локальных онтиму-мов обладают классы с наиболее жесткими ограничениями по ресурсам. Примеры с менее жесткими ресурсными ограничениями обладают малым числом локальных оптимумов. В частности, в случае когда имеющихся ресурсов достаточно для выполнения всех работ, локальный оптимум всегда один. Он же является и глобальным. Это объясняется тем, что соседние решения относительно рассматриваемых окрестностей являются активными расписаниями. Нетрудно показать, что в примерах с неограниченными ресурсами всякое активное расписание является оптимальным.

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

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

Рис. 1: Концентрация локальных оптимумов

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

В разделе 2.1 приводится метод параллельного составления расписаний9 как основа большинства жадных алгоритмов. Метод последовательно строит расписание, добавляя в него очередные работы. Число шагов не превосходит п. На шаге т рассматривается момент времени (т и три множества: ./(£„,) — множество работ, завершенных к моменту времени гт, п) — множество работ, находящихся в процессе выполнения в момент времени Ьт и 1?(£т) — множество работ, готовых к выполнению в момент времени

Если множество не пусто, то из него выбирается несколько ра-

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

9 Kolisch R. Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation // European J. Oper. Res. 1996. V. 90. P. 320-333.

Алгоритм МПР:

1. Положить т := 0, tm := 0, J(tm) 0, A{tm) := {1}, с\ := 0.

2. Пока | J(tm) + A(l„,)\ < п выполнять следующее:

2.1 Положить ш := т + 1.

2.2 Найти trn := min{cj | j G A(ira_i)}.

2.3 Вычислить J(tm), A(tm), D(tm).

2.4 Выбрать D' С D(tm) так, что rjk < Rk - EjeA(tm) rjb к e K.

2.5 Положить Sj := tm, j €

Стратегия выбора подмножества D' С £)(tm) на шаге 2.4 является наиболее важным аспектом этого подхода. Произвол в выборе искомого множества открывает широкие перспективы для развития жадных эвристик на основе алгоритма МПР.

В разделе 2.2 описываются три вероятностные жадные стратегии выбора подмножества D'. Согласно первой стратегии, для каждой работы из D(tm) определяются временные задержки относительно наиболее поздних моментов старта в задаче без ресурсных ограничений. Идея этой эвристики состоит в ранжировании работ по временным задержкам. Наибольший приоритет получают работы с большими задержками. Вторая стратегия использует подобную идею, но в отличие от предшествующей стратегии здесь формулируется оптимизационная задача на узкое место, в которой ресурсные ограничения учитываются явным образом. В работе показано, что задача на узкое место является полиномиально разрешимой. Тем не менее, оптимальных решений может быть экспоненциально много, и они могут существенно отличаться по числу параллельно выполняемых работ и использованию ресурсов. Поэтому среди оптимальных решений выбирается решение с минимальными остатками ресурсов. Основная идея третьей стратегии — использовать имеющиеся ресурсы в максимально полном объеме. Эта идея формулируется в виде задачи о многомерном рюкзаке, которая является NP-трудной. Однако точное решение в данном случае не требуется. Для вероятностных жадных методов важно иметь много разных приближенных решений. Для задачи о рюкзаке уже разработаны жадные эвристики10. В повой эвристике используются их вероятностный аналог с обобщением на многомерный случай.

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

10 Martello S., Toth P. Knapsack problems. Algorithms and computer implementations. Chichester: John Wiley к Sons, 1990.

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

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

В третьей главе исследуется метод поиска с запретами, использующий идею чередования окрестностей.

В разделе 3.1 рассматривается две окрестности, NA(S) И NT(S). Первая из них строится для активных расписаний, вторая — для Т-поздних. Активные и Т-ноздиис расписания удачно дополняют друг друга и переход от одной окрестности к другой привносит определенное разнообразие в локальный поиск, что благотворно сказывается па результатах работы алгоритма.

В разделе 3.2 приводится общая схема алгоритма. Разработанный алгоритм сочетает в себе идеи двух методов: локальный поиск по переменной окрестности12 и поиск с запретами13. За основу принята схема поиска с

11 Кочетов Ю. А., Столяр А. А. Использование че^дующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискрет, анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 2. С. 29 55

12 Напьеп Р., Mladenovií N. Developments of variable neighborhood search // Essays and Surveys of Metaheuristics. Boston: Kluwer Acad. Puhl., 2002. P. 415-440.

n Glover F., Laguna M. Tabu search. Boston: Kluwer Acad. Puhl., 1997.

запретами, в которой систематически осуществляется переход от окрестности к Л^г(5) и наоборот. На каждом шаге этой процедуры имеется некоторое расписание 5 и значение функции /(5) = 8} от расписаний, полученных на последних к шагах алгоритма. Набор таких значений будем называть списком запретов. Шаг алгоритма состоит в переходе от расписания 5 к соседнему расписанию 5'по окрестности НА(5) ИЛИ N1(5). Для окрестности формируется случайным образом ее непустое подмножество или N^(3), из которого выбирается расписание с минимальным значением целевой функции. Подмножество формируется следующим образом. Из окрестности N¿(3) (Л^г(5')) удаляются все расписания, для которых значение функции /(5) совпадает с одним из значений в списке запретов. Затем каждое из оставшихся расписаний включается в множество ЛГд(5) с некоторой вероятностью д. Если длина списка запретов велика, то в результате удаления из окрестности "запрещенных "элементов, она может оказаться пустой. В этом случае длина списка запретов уменьшается. Если подмножество iУд(S') (Т\^(5)) оказалось пустым, то в него добавляется произвольный незапрещепиый элемент из окрестности .Л?а(3) (Лгг(5')).

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

В четвёртой главе рассматривается эволюционный алгоритм. Алгоритм представляет собой итерационный случайный процесс, оперирующий с набором особей - популяцией. Каждая особь является допустимым решением рассматриваемой задачи. Стандартный эволюционный алгоритм начинает свою работу с формирования начальной популяции РОРо = {¿>1, £?2, - - ■ > ¿т} - конечного набора допустимых решений задачи. Эти решения могут быть выбраны случайным образом или получены с помощью эвристических методов, например вероятностного жадного алгоритма. Эволюционный алгоритм состоит из трех основных этапов: отбора кандидатов, операции скрещивания и обновления популяции. В ходе отбора кандидатов выделяется часть популяции, содержащая наиболее "перспективных" родителей для достижения желаемого результата. К данной элите применяется операция скрещивания, в результате которой порождаются новые особи. Популяция, таким образом, увеличивается. Чтобы вернуть ей исходный размер применяется процедура обновления, которая отсеивает наименее подходящие решения. Затем описанные три этапа повторя-

ются снова, формируя эволюционный процесс, продолжающийся пока не выполнен критерий остановки.

В разделе 4.1 предлагается новый оператор скрещивания, основанный на известной стратегии связывающих путей. Согласно этой стратегии, по выбранной парс "родителей" строится некоторый набор решений — связывающий путь. На этом пути выбирается повое решение, которое добавляется в популяцию с последующей операцией отбора. В отличие от генетического алгоритма, число потомков, генерируемое на текущем этапе эволюции, относительно мало. Это обстоятельство позволяет успешно использовать эволюционный алгоритм в сочетании с локальным поиском на большую глубину, таким как поиск с запретами, имитация отжига, поиск по переменной окрестности и т.п. В разделе 4.3 обсуждаются преимущества такой комбинированной стратегии.

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

• сокращения расстояния до другого списка,

• минимизации длины расписания.

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

В разделе 4.3 обсуждаются результаты численных экспериментов. Приводится сравнение нового оператора скрещивания с известными ранее. Обсуждаются четыре способа выбора порождающей пары. Исследуется влияние начальной популяции на эволюционный процесс. Приводятся результаты сравнения нового алгоритма с уже известными. Один из основных результатов работы состоит в получении 28 допустимых решений с новыми рекордными значениями целевой функции для наиболее трудных тестовых примеров из международной библиотеки Р8РЫЬ.

В заключении приводится перечень основных результатов диссертации.

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

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

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

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

Основные результаты диссертации опубликованы в работах:

1. Кочетов Ю. А., Столяр А. А. Алгоритм поиска с запретами для задачи календарного планирования с ограниченными ресурсами // Сборник тезисов конференции "Дискретный анализ и исследование операций", 2000. С. 187.

2. Столяр А. А. Задача календарного планирования с ограниченными ресурсами: исследование окрестностей для локального поиска // Труды XII Байкальской международной конференции 2001. Т. 6. С. 46-50.

3. Столяр А. А. Стратегия связывающих путей для задачи календарного планирования с ограниченными ресурсами // Сборник тезисов конференции "Дискретный анализ и исследование операций", 2002. С. 238.

4. Кочетов Ю. А., Столяр А. А. Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискрет, анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 2. С. 29-55.

5. Кочетов Ю. А., Столяр А. А. Локальный поиск с экспоненциальной окрестностью для задачи календарного планирования с ограниченными ресурсами // Сборник тезисов конференции "Проблемы оптимизации и экономические приложения", 2003. С.98.

6. Столяр А. А. Эволюционный поиск с запретами для задачи календарного планирования с ограниченными ресурсами // Сборник тезисов конференции "Математическое программирование и приложения", 2003. С. 218.

7. Кочетов Ю. А., Столяр А. А. Вероятностный адаптивный поиск для задачи календарного планирования с ограниченными ресурсами // Сборник тезисов конференции "Дискретный анализ и исследование операций", 2004. С. 188.

8. Kochctov Yu, Stolyar A. Distribution of Local Optima for the Resource Constrained Project Scheduling Problem // Book of abstracts of International Conference on Operations Research, Duisburg, Germany, 2001, p.80.

9. Kochctov Yu., Stolyar A. Evolutionary Tabu Search for the Resource Constrained Project Scheduling Problem // Book of abstracts of Joint International Meeting EURO/INFORMS, Istanbul, Turkey, 2003. p. 208.

10. Kochetov Yu., Stolyar A. Evolutionary local search with variable neighborhood for the resource constrained project scheduling problem // Proc. of 3-th Intern. Workshop of Computer Science and Information Technologies. Extended Abstracts (Ufa, Russia, September 16-18, 2003). P. 9699.

11. Kochctov Yu., Stolyar A. A probabilistic multi-pass heuristic for the resource constrained project scheduling problem // Proc. of 9-th Intern. Workshop on Project Management and Scheduling. Extended Abstracts (France, April 26-28, 2004). P. 319-322.

12. Kochctov Yu., Stolyar A. A GRASP approach to the resource constrained project scheduling problem // Proc. of 2-th Intern. Workshop on Discrete Optimization Methods in Production and Logistics. Extended Abstracts (Omsk-Irkutsk, Russia, July 20-27, 2004). P. 131-136.

Столяр Артем Александрович

Алгоритмы локального поиска

для задачи календарного планирования

с ограниченными ресурсами

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Подписано в печать 24.05.2005. Формат 60x84 1/16. Печать офсетная. Усл. печ. л. 1. Уч.-изд. л. 0,8. Тираж 80 экз. Заказ № 15508.

13 ИЮЛ 2005

Кс

Лицензия ПЛР 060403 от 06.06.1999 Отпечатано ЗАО "Локус стаиди" 129272 Москва, Олимпийский просп., 32.

Введение

Глава 1. О концентрации локальных оптимумов

1.1. Окрестности

1.1.1. Окрестность Ni(S)

1.1.2. Окрестность ^(S)

1.1.3. Окрестность .•.

1.1.4. Задача о многомерном рюкзаке

1.2. Библиотека тестовых задач

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

1.3.1 Исследование зависимости числа локальных оптимумов от входных данных задачи

1.3.2. Исследование концентрации локальных оптимумов

Глава 2. Новые жадные алгоритмы

2.1. Метод параллельного составления расписаний

2.2. Вероятностные жадные стратегии .>.

2.2.1. Сортировка по временным задержкам

2.2.2. Использование решения задачи на узкое место

2.2.3. Использование решения задачи о многомерном рюкзаке

2.3. Локальные улучшения

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

2.4.1. Сравнение жадных стратегий

2.4.2. Внесение рандомизации

2.4.3. Локальный спуск.

2.4.4. Сравнение с другими алгоритмами

Глава 3. Поиск с запретами и чередованием окрестностей

3.1. Окрестности

3.2. Общая схема

3.2.1. Построение начального решения.

3.2.2. Вероятностный поиск с запретами

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

3.3.1. Эффект чередующихся окрестностей

3.3.2. Размер окрестности и ее рандомизация

3.3.3. Влияние списка запретов

3.3.4. Выбор начального решения

3.3.5. Интенсификация поиска

1 v 3.3.6. Сравнение с другими алгоритмами

Глава 4. Эволюционные алгоритмы

4.1. Стратегия связывающих путей

4.2. Построение связывающего пути

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

4.3.1. Свойства оператора скрещивания.

4.3.2. Выбор порождающей пары

4.3.3. Выбор начальной популяции

4.3.4. Комбинация с локальным поиском.

4.3.5. Сравнение алгоритмов локального поиска.

4.3.6. Сравнение с мировым уровнем.

Задачи календарного планирования отражают процесс распределения во времени ограниченного числа ресурсов для выполнения проекта, состоящего из заданного множества взаимосвязанных работ. Это известная NP-трудная задача дискретной оптимизации [5], исследуемая более сорока лет. На сегодняшний день она широко используется в таких областях как строительство, военная промышленность, разработка программного обеспечения и т.д. Кроме того, данная задача представляет интерес с математической точки зрения, поскольку календарное планирование содержит достаточно богатый класс известных сложных задач теории расписаний, а также тесно связано с задачами раскроя и упаковки.

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

Известно, что для ЗКПОР маловероятно существование приближенного полиномиального алгоритма с гарантированной оценкой точности порядка 0(п1е) для любого е > 0 [76]. Данное обстоятельство вызывает особый интерес к приближенным методам, среди которых следует отметить жадные алгоритмы, алгоритмы локального поиска, а также их вероятностные варианты.

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

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

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

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

Проведены численные эксперименты на примерах из международной библиотеки тестовых задач PSPLib [66]. Результаты показали, что разработанный алгоритм является лучшим среди опубликованных эвристических методов. Для 28 тестовых примеров этой библиотеки алгоритмом были получены новые рекордные значения целевой функции.

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

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

В первой главе приводится численное исследование концентрации ло кальных оптимумов в задаче календарного планирования с ограниченным* ресурсами. Исследуется число различных локальных оптимумов относительно трех рассматриваемых окрестностей в различных классах тестовы> примеров. Обсуждается вопрос относительно взаимного расположения локальных оптимумов.

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

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

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

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

Основные результаты диссертации опубликованы в работах [6, 7, 8, 9 10,11, 12, 53, 54, 55, 56; 57] и докладывались на Международной конферен ции "Дискретный анализ и исследование операций"(г. Новосибирск, 2000 2002, 2004), на 12-й Международной Байкальской конференции (г. Ир кутск, 2001), на Симпозиуме по исследованию операций (г. Дуйсбург, Гер мания, 2001), на конференции "Математическое программирование и приложения" (г. Екатеринбург, 2003), на Международной объединенной кон ференции по исследованию операций EURO/INFORMS (г. Стамбул, Турция, 2003), на 9-й международной конференции по задачам календарног " планирования PMS'04 (г. Нанси, Франция, 2004), на научных семинарах в Институте математики им. C.JI. Соболева СО РАН.

0.1 Математическая постановка задачи

Обозначим через J = {1,., n}U {0, n+1} множество работ, в котором 0-я и (п + 1)-я работы являются фиктивными и задают начало и завершение всего проекта. Они имеют нулевую длительность. Для каждой работы j 6 J время ее выполнения обозначим через pj > 0, ро = Pn+i = 0. Отношения предшествования на J зададим совокупностью множеств Pj, содержащих всех непосредственных предшественников работы j, j 6 J. Если i € Pj, то работа j не может начаться до завершения работы г. Предполагается, что 0 е Pj и j е Рп+1 для всех j G {1,., п}.

Через К = {1,., К} обозначим множество ресурсов, необходимых для выполнения работ множества J. Все ресурсы предполагаются возобновляемыми и нескладируемыми [1], то есть в каждый момент времени выделяется определенный объем ресурсов каждого типа, а остатки ресурсов пропадают. В рассматриваемой постановке задачи выделяемый ресурс Rk > 0, к G К есть величина постоянная. Через > 0 обозначим объем к-го ресурса, необходимый для выполнения j-й работы в каждый момент ее выполнения.

Введем переменные задачи. Через Sj > 0 обозначим момент начала выполнения j-й работы. Так как работы выполняются без прерывания, то момент окончания работы Cj > 0 определяется равенством Cj = Sj+pj. Через .A(t).— {j € J | Sj < t < Cj} обозначим.множество работ, находящихся.в процессе выполнения в момент времени t. Время завершения проекта для расписания S = {Sj, j G J} обозначим через T(S). Эта величина соответствует времени завершения последней работы проекта, T(S) = Сп+С использованием данных обозначений задача календарного планирования с ограниченными ресурсами записывается следующим образом.

Найти : minT(S) при ограничениях с% < Sj, % е Pj, j е J J2 rkj <Rk, кеК, t> o,

JeA(t)

Sj > 0.

Целевая функция задает время завершения проекта. Первое ограничение соответствует условиям предшествования, второе — выделяемым ресурсам.

Сформулированная задача, как обобщение известной задачи Job-Shop, относится к классу NP-трудных задач дискретной оптимизации [25]. Известно, что для задачи календарного планирования с ограниченными ресурсами маловероятно существование приближенного полиномиального алгоритма с гарантированной оценкой точности порядка п1-£ для любого е > 0. Более точно это утверждение выглядит следующим образом.

Теорема 1 [76] Для ЗКПОР не существует полиномиального приближенного алгоритма с гарантированной оценкой точности порядка п1~е для любого е > 0, если NP ф ZPP.

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

0.2 Точные методы

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

0.2.1 Дерево предшествований

В работе [85] предлагается алгоритм, основанный на так называемом дереве предшествований. Процедура начинается с присвоения начальной фиктивной работе нулевого момента начала. На каждом уровне т дерева ветвления рассматривается множество работ Jm, включенных в расписание, а также множество допустимых работ Dm = {j \ Pj С Jm}, предшественники которых принадлежат множеству Jm. Далее выбирается допустимая работа j, для которой вычисляется наиболее ранний момент начала Sj в соответствии с условиями предшествования и ограничениям по ресурсам. Затем процесс ветвления переходит на следующий уровень. Как только в качестве допустимой работы выбирается последняя фиктивная работа п + 1, получено полное расписание (висячая вершина) и процесс поднимается на уровень выше с переходом к следующей допустимой работе. Как только просмотрены все допустимые работы данного уровня, процесс переходит еще на уровень выше. В результате получается дерево, где всякий путь из корня в висячую вершину представляет собой допустимую по условиям предшествования перестановку работ. В последствии этот алгоритм был модернизирован с помощью эффективной технологии сокращения дерева поиска [92].

0.2.2 Выбор с задержкой

Этот алгоритм был предложен в работе [31]. В отличие от предыдущего алгоритма, на каждом уровне т рассматривается момент времени tm как потенциальный момент начала некоторых работ. Не включенная в расписание работа j является допустимой в момент tm, если все ее предшественники г S Pj включены в расписание и заканчиваются до текущего момента, т.е. С{ < tm, г G Pj. Множество A(tm) = {j \ Sj < tm < Cj} содержит работы, находящиеся в процессе выполнения в момент времени tm. Момент tm определяется как минимальный момент завершения работ, выполняемых в момент tm-1, т.е. tm = min{cj | j G A(tm-1)}. Далее строится множество допустимых работ Dm, которое затем добавляется к множеству выполняемых работ A(tm). В результате могут быть нарушены ограничения по ресурсам. Следовательно, чтобы сохранить допустимость, какие-то работы необходимо задержать. Через DA(tm) обозначено подмножество A(tm), для которого выполняется условие J2j^A{tm)\DA{tm) rjk ^ Дь Для всех к € К. Множество DA(tm) выбирается минимальным по включению. Ветвление соответствует альтернативному выбору множеств DA(tm). Как только получено полное расписание, процесс возвращается на уровень выше и переходит к следующей альтернативе.

0.2.3 Выбор с расширением

Метод, предложенный в работе [96], отличается от предыдущего выбором альтернативы. По-прежнему рассматриваются множества Dm и A(tm). Однако в отличие от предыдущего метода, они не объединяются. Вместо этого строится множество EA(tm) как подмножество допустимых работ, которые могут выполняться параллельно с работами из множества A(tm), не нарушая ограничений по ресурсам, т.е. HjeA(tm)\jEA(tm)rjk < Rk- Ветвление происходит по различным множествам EA(tm). Еще одно отличие состоит в том, что при переходе на следующий уровень т + 1 все работы из множества A(tm) остаются в расписании, в то время как в предыдущем методе некоторые из них могут быть временно исключены из расписания.

0.2.4 Выбор на основе логической схемы

В методе, предложенном в работе [29], вместо частичных расписаний рассматриваются логические схемы, определяемые следующим образом. Схема (С, D, N, F) состоит из четырех отношений на множестве J. Отношения в С называются конъюнкциями и обозначаются через (г —> j). Для таких работ выполнено Cj < Sj. Отношения в D называются дизъюнкциями, и обозначаются через (г — j). Сюда относятся работы, для которых выполнено либо (г -> j), либо (j —г). Множество N содержит пары работ, которые выполняются параллельно в течение некоторого периода времени. Все остальные пары лежат в F.

Если Со — множество пар, связанных условиями предшествования, Do — множество пар, которые не могут выполняться одновременно ввиду ограничений по ресурсам, a Fq — множество всех оставшихся пар, то схема (Со, D0, 0, Fo) будет выступать в качестве корневой вершины в дереве поиска. Ветвление происходит путем перемещения пары из F в D, либо в N. С помощью специальных правил [29] удается пополнить множества С, D, и iV, сокращая тем самым дерево поиска.

0.2.5 Представление в виде задачи ЦЛП

Одним из способов решения ЗКПОР является применение пакета CPLEX [24] к формулировке в виде задачи целочисленного линейного программирования (ЦЛП) [88]. Для каждой работы i € J определяется окно ее выполнения [esj, lsi\. Границы окна обозначают, соответственно, наиболее раннее и наиболее позднее время начала работы г. Положив eso = 0 и lsn+1 = Ттах, некоторой верхней оценке на длину расписания, значения [es* и ls{] определяются для всех г G J согласно условиям предшествования по рекуррентным формулам [39]. Расписание определяется значениями булевых переменных £ {0,1}: значение переменной равно единице тогда и только тогда, когда работа г начинается в момент времени t, i 6 J, t = es{,., ls{. С учетом введенных обозначений формулировка в задачи ЦЛП записывается следующим образом. Найти : lsn+1 min 1' t t=esn+i при ограничениях

Isi = l, ie J, t=esi lsi 1st - pi>г 6 t=esj t=esi t

YJ Tik < Rk, t = o,., Tmax, к e K, ieJ T=a(t,i) {о, 1 },ie J, t = esi,., hi, где a{t,г) = max{0, t-pi-f 1}. Первое ограничение запрещает прерывания. Второе и третье соответствуют условиям предшествования и ограничениям по ресурсам.

0.3 Метод Т-поздних расписаний для задачи со складируемыми ресурсами

Ресурс называется складируемым, если он, будучи неистраченным в момент времени t, может быть использован в момент времени t' > t. Если все ресурсы являются складирумыми, удается построить точный полиномиальный алгоритм [1].

Определение 1 Допустимое расписание называтся Т-поздним, если для всех работ j 6 J и некоторого Т выполнено Sj -f pj < Т и увеличение любого из моментов Sj приводит к нарушению этого неравенства либо условий предшествования.

Очевидно, что длина Т-позднего расписания не превосходит Т. Такое расписание может быть построено с помощью следующих рекуррентных соотношений: sn+i = Т, Sj = min{sj | г G Sj} — pj, где Sj - множество непосредственных последователей работы j.

Теорема 2 [1] Пусть Т* — длина оптимального расписания. Тогда существует допустимое Т*-позднее расписание.

Если pj — целые числа, то данное утверждение позволяет искать оптимальное расписание среди Т"-поздних методом дихотомии. Пусть Т\ и Тг соответственно нижняя и верхняя оценка длины допустимого расписания. Тогда оптимальное расписание может быть получено с помощью следующего алгоритма [2].

1. Положить [Т = (Ti + Г2)/2].

2. Построить Т-позднее расписание {^J}.

3. Если расписание {sj} допустимо, то положить Т\ = Т, иначе положить = Т.

4. Если Т2 — Т\ > 1, то перейти на шаг 1, иначе получено оптимальное расписание {sj1}.

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

0.4 Приближенные методы 0.4.1 Декодирующие процедуры

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

Последовательная процедура

Последовательная процедура состоит из п + 2 шагов. На каждом шаге т рассматривается множество Jm работ, уже включенных в расписание, и остаточный объем имеющихся ресурсов в каждый момент времени Rk{t) —

Rk~ rjk- Шаг состоит в добавлении в расписание очередной работы из jeA(t) множества Dm = {j G J \ Jm \ Pj С Jm}, которое будем называть допустимым множеством. Алгоритм построения расписания может быть записан следующим образом.

Последовательный декодер:

0. Положить со = 0, Jo = {0}.

1. Для всех т = 1,., п + 1 выполнять следующее:

1.1 Вычислить Dm, Rk(t).

1.2 Выбрать работу j £ Dm.

1.3 Вычислить наиболее ранний момент Sj начала работы j, G Dm, допустимый по условиям предшествования и ограничениям по ресурсам

1.4 Положить Jm = Jm~i\J{j}.

2. Положить T(S) = sn+1.

Трудоемкость процедуры оценивается величиной 0(п2К). Полученное таким образом расписание относится к классу активных расписаний [60].

Определение 2 [93] Активным называется такое расписание, в котором ни одна работа не может быть начата раньше указанного ей срока без нарушения условий предшествования либо ограничений по ресурсам.

Теорема 3 [60] Класс активных расписаний содержит оптимальное расписание.

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

Т-поздняя процедура

Т-поздняя процедура является аналогом последовательной ДП и строит расписание в обратной последовательности. На первом шаге фиксируется число Т и полагается Сп+\ = Т. Далее на каждом шаге m = п,., 1 рассматриваются аналогичные множества Jm и Rk(t) = Rk~ rjk• Д° jeA{t) пустимое множество Dm = {j G J \ Jm | Sj С Jm} состоит из работ, последователи которых включены в расписание.

Т-поздний декодер(Т):

0. Положить sn+i := Cn+i := Т. :>,V: Для всех-m = n,., 0 выполнять следующее:

1.1 Вычислить Dm, Rk(t).

1.2 Выбрать работу j 6 Dm.

1.3 Вычислить наиболее поздний момент Cj завершения работы j, G Dm, допустимый по условиям предшествования и ограничениям по ресурсам

1.4 Положить Sjm = Cj — pjm.

1.5 Положить Jm = Jm+1 (JO"}-3. Вычислить T(S) ==Т — so.

Трудоемкость процедуры также оценивается величиной 0(п2К). Если ограничения по ресурсам не зависят от времени, то среди Т-поздних расписаний найдется и оптимальное. Доказательство проводится аналогично случаю с активными расписаниями.

Параллельная процедура

Последовательная ДП поочередно рассматривает работы проекта и для каждой из них подбирает момент ее начала. Параллельная процедура поступает иначе. На каждом шаге т = 1,., п рассматривается момент времени tm, и по нему строится множество работ, которые будут начинаться в указанный момент времени. Обозначим через J(tm) = {j G J | Cj = tm} множество работ, завершенных к моменту времени tm и через D(tm) = {j G J \ J{tm) | Pj Я J{tm), Tjk < Rk{tm)} — допустимое множество работ, где Rk(tm) — остаточный объем ресурсов в момент tm. С учетом введенных обозначений, параллельная процедура выглядит следующим образом.

Параллельный декодер:

0. Положить т = 0, tm = 0, А(0) = {0}, J(0) = {0}, Дь(0) = Rk.

1. Пока \A(tm) (J J(tm)\ < п выполнять следующее:

1.1 Положить т = m + 1.

1.2 Положить tm = min{cj | j G

1.3 Вычислить J(tm), A(tm), Rk{tm), D(tm).

1.4 Пока D(tm) ф 0 выполнять следующее:

1.4.1 Выбирать работу j G D(tm).

1.4.2 Положить Sj = tm.

1.4.3 Обновить Rk{tm), A{tm), D(tm).

2. Положить T(S) = max{cj | j G J}.

Трудоемкость процедуры также оценивается величиной 0(п2К). Полученное таким образом расписание относится к классу плотных расписаний [60], который является подклассом активных расписаний.

Определение 3 [93] Активное расписание называется плотным, если при замене каждой .работы j G J на pj работ единичной длительности оно остается активным.

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

0.4.2 Кодировки решений

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

Список

Значительная часть работ, посвященных алгоритмам решения ЗКПОР, использует кодировку решения в виде списка L = (ji,.,jn). Предполагается, что списки согласованы с условиями предшествования, то есть для любой пары (i,j), г € Pj позиция работы j больше позиции работы г. По списку строится расписание с помощью вышеописанных декодирующих процедур. Последовательный декодер согласно списку последовательно вычисляет наиболее раннее время начала выполнения каждой работы, учитывая ресурсные ограничения. Для Т-позднего декодера фиксируется длина расписания Т, и для каждой работы согласно списку вычисляется наиболее позднее время ее окончания с учетом ресурсных ограничений. Как было сказано выше, условия предшествования учитываются при составлении списка, что позволяет избежать их проверки при декодировании. В схеме параллельного декодера на шаге 1.4.1 из допустимого множества выбирается работа с наименьшей позицией в списке.

Вектор значений приоритета

Для решения задач теории расписаний интенсивно исследовались быстрые полиномиальные алгоритмы, основанные на приоритетных правилах. Согласно этому подходу, среди множества работ, доступных к выполнению, выбирается одна работа по заданному критерию, например, работа с минимальной длительностью, минимальным числом предшественников или другому критерию. Понятно, что ни одно из таких правил не гарантирует получения оптимального решения, если задача является iVP-трудной. Поэтому более эффективной стратегией является применение сразу нескольких приоритетных правил и использование одного из них в зависимости от уже построенного частичного расписания. Идея такой групповой стратегии применялась и для ЗКПОР [26, 99]. Кодировка решений задается вектором 7Г = (7Г1,. ,7ГП), где щ определяет приоритетное правило выбора очередной работы. Отметим, что такая кодировка, как и предыдущая, позволяет за полиномиальное время получить расписание работ, но одному расписанию может соответствовать несколько разных векторов тт.

Вектор смещения

В работе [90] было предложено представление решений в виде вектора смещения. Решение задается вектором целых неотрицательных чисел а .= (<7i,. , <тп). Декодирующая процедура последовательно вычисляет величины Sj как максимум по всем моментам завершения предшественников работы j, к которым добавляются некоторые величины задержки cry, т. е. Sj — max{sj -f pi | i € Pj] + aj, j = 1 Поскольку декодирующая процедура не учитывает ограничения по ресурсам, то полученное расписание может оказаться недопустимым. В этом случае к длине расписания добавляется величина штрафа, которая зависит от степени нарушения ресурсных ограничений.

Логическая схема

Для переборных методов типа ветвей и границ была предложена специальная кодировка решений, ориентированная на анализ условий предшествования и'Ограничений по ресурсам. [29]. Эта кодировка получила на-, звание логическая схема. Она представляет собой четверку непересекающихся отношений (С, D, iV, F). Множество С задает исходные условия предшествования. Если (i,j) 6 D, то работы г и j не могут пересекаться по времени. Если (i,j) G N, то работы г и j должны выполняться параллельно в течение хотя бы одной единицы времени. Множество F содержит все оставшиеся пары (i,j), которые не противоречат множествам С, D и N. Конкретная четверка (С, D, N, F) является кодом всех расписаний, в гкоторых выполняются все отношения из С, -0,-и N. В качестве декодирующей процедуры была разработана эвристика [29], строящая расписание, удовлетворяющее отношениям из С и D и большей части отношений из N. Следует отметить, что вопрос о существовании допустимого расписания, удовлетворяющего фиксированной схеме является АГР-полной задачей [69].

Кроме перечисленных существует и кодировка в виде набора булевых переменных £jt € {0,1}, £jt = 1 Sj = t. Такая кодировка использовалась в алгоритме лагранжевой релаксации [76] для формулировки ЗКПОР в виде задачи ЦЛП.

0.4.3 Методы приоритетных правил

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

Приоритетные правила

Исследованиям в области приоритетных правил для ЗКПОР посвящено колоссальное число работ [18, 26, 34, 33, 35, 36, 40, 58, 59, 60, 70, 80, 82, 83, 84, 91, 97, 99, 102, 106, 108]. Приоритетное правило ставит в соответствие каждой работе j Е Dm некоторое число Vj. В ходе построения расписания при выборе очередной работы из допустимого множества определяющим фактором является указанное значение приоритета.

Приоритетные правила обычно классифицируют по трем критериям. По типу " информации, необходимой для вычисления значения приоритета правила делятся на сетевые, временные и использующие ограничения по ресурсам [18, 70]. По количеству используемой информации различают глобальные и локальные правила. В локальных правилах необходима лишь информация об одной работе, для которой определяется значение приоритета, например, длительность выполнения, в то время как в глобальных правилах необходим больший объем данных. Деление на статические и динамические правила основывается на том, зависит ли определяемое значение приоритета от предыстории построения текущего расписания или же способ его определения всегда одинаковый. Наконец, правило может предполагать использование как только одного декодера, так и нескольких.

Примеры наиболее известных приоритетных правил приведены в Приложении А: наибольший позиционный вес (GRPW — greatest rank positional weight), наиболее поздний момент завершения (LFT: latest finish time), наиболее поздний момент начала (LST: latest start time), минимальный резерв (MSLK: minimum slack), максимум всех последователей (MTS: most total successors), метод распределения ресурсов (RSM: resource scheduling method), минимальное время выполнения (SPT: shortest processing time), резерв в худшем случае (WCS: worst case slack). Правило MTS использует множество Sj — транзитивное замыкание множества непосредственных последователей работы j Е J. Для определения правил WCS и RSM вводится множество пар работ АР = {() 6 Dm х Dm | i ф j} — декартово произведение допустимого множества за вычетом диагонали. Правило WCS использует величину E(i,j) — наиболее ранний момент начала работы J G J, допустимый по условиям предшествования и ограничениям по ресурсам, при условии, что работа i G J начата в момент времени tm. Это правило предполагает использование только параллельного декодера.

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

Одношаговые методы

К классу одношаговых методов относится большинство детерминированных жадных алгоритмов. Их основная идея состоит в построении одного расписания, используя последовательную или параллельную декодирующую процедуру в соответствии с заранее определенным правилом приоритета. Примеры таких алгоритмов описаны в работах [18, 26, 33, 34, 35, 36, 40, 58, 60, 70, 83, 84, 97, 106, 108].

Значительно позже были разработаны более сложные приоритетные правила как, например, WCS для параллельного декодера [60]. В работах [82, 102] описывается приоритетное правило, получившее название анализа на основе локального ограничения (LGBA: local constraint based analysis). Правило LCBA предполагает использование параллельного декодера и на основе имеющейся информации о потреблении ресурсов в момент времени tm принимает решение о том, какие работы допустимого множества D(tm) необходимо начать в момент tm.

Многошаговые методы

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

Методы, использующие несколько правил Для ЗКПОР известен достаточно широкий спектр приоритетных правил. Тем не менее, нельзя утверждать, что одно правило заведомо лучше другого. Как показывают исследования [61, 94, 95], разные правила, используемые в схеме одного алгоритма, обладают переменным успехом в зависимости от специфики исходных данных тестовой задачи. Поэтому многие авторы предлагают использовать несколько правил для получения нескольких расписаний. Так, например, в работе [26] предлагается алгоритм, использующий 7 различных правил. Недостатком такого подхода является то, что число построенных таким образом расписаний не превосходит числа использованных правил. В качестве одного из способов преодолеть этот недостаток предлагается заменить использование т правил для получения т расписаний на их выпуклую комбинацию v(j) = J^Li wi' vi{j)> гДе wi > 0, Vi и Ylu= 1 wi = 1) как, например в работах [99, 102]. Этот прием позволяет строить любое наперед заданное число расписаний.

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

Вероятностные многошаговые методы Данная категория алгоритмов включает большинство известных вероятностных жадных алгоритмов для решения ЗКПОР. Такие алгоритмы, как правило, представляют собой серию из независимых испытаний, в ходе каждого из которых строится расписание с внесением элемента случайности. В качестве результата выступает лучшее расписание из указанной выборки. В отличие от предыдущих методов для работ допустимого множества вместо значений приоритета строится вероятностное распределение {pr(j), j £ Dm}, X^e£>mPrC?) = 1-На каждом шаге построения расписания очередная работа выбирается случайным образом согласно указанному распределению. Наиболее простым является равновероятный выбор работ, т.е. когда pr[j) = l/\Dm\ для всех j £ Dm. В иностранной литературе такой способ известен под названием Random sampling. Недостатки такого подхода очевидны. Хотя он и обеспечивает необходимое разнообразие, но тем не менее практически не использует информацию об исходных данных задачи. В работах [19, 34] было предложено использовать распределение на основе значений приоритета. Вероятности pr(j) определялись пропорционально величинам v(j) с целью отдавать предпочтение работам с большими значениями приоритетов. Интересное сочетание приоритетов и разнообразия используется в алгоритме, предложенном в работе [95]. Для определения вероятностей pr(j) авторы предлагают использовать нормальное распределение, равновероятно выбирая работы с минимальным и максимальным значением приоритета.

Согласно исследованиям, проведенным в [59, 95], наиболее часто наилучшими вероятностными многошаговыми методами оказываются эвристики, в которых при определении вероятностей pr(j), j £ Dm используется так называемое распределение на основе худшего [38]. Для каждой работы j £ Dm определяется разность r(j) = v(j) — min г>(г) между ее значением ieDm приоритета и наименьшим значением среди всех работ допустимого множества. Далее, определяются величины r'(j) = (r(j) + е)а, пропорционально которым вычисляются соответствующие вероятности pr(j), j £ Dm. Добавление величины б > 0 гарантирует положительную вероятность для каждой работы допустимого множества и, тем самым, с ненулевой вероятностью позволяет построить любое допустимое расписание. Выбор значения параметра се контролирует степень рандомизации. При больших значениях а поведение алгоритмов подобно детерминированным, поскольку работы с наибольшим значением приоритета будут всегда получать несравнимо большую вероятность выбора. При аг = 0 достигается наибольший произвол, т.к. в этом случае все работы выбираются равновероятно.

В работе [61] был предложен адаптивный многошаговый метод. За основу были взяты последовательный декодер с правилом LFT и параллельный декодер с правилом WCS. Адаптивность метода обусловлена выбором одного из двух указанных вариантов при каждом построении нового расписания. Этот выбор зависел как от исходных данных задачи, так и от числа уже построенных расписаний. Этот алгоритм был в дальнейшем модифицирован [94] путем динамического определения параметра е и увеличения числа используемых приоритетных правил.

0.4.4 Метаэвристики

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

Имитация отжига Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году [52]. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость.

Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма в окрестности текущего решения Sk выбирается некоторое решение 5', и если разность по целевой функции между новым и текущим решением не превосходит заданного порога Tfc, то новое решение S' заменяет текущее. В противном случае выбирается новое соседнее решение.

Алгоритм, предложенный в работе [30], использует кодировку решения в виде вектора значений приоритета. Элемент окрестности определяется по двум работам i,j 6 «/, для которых значения приоритета в соседнем решении меняются друг с другом. При этом работа г выбирается случайно из всего множества работ, а работа j — только из некоторой его части, определяемой работой г.

Алгоритм [28] использует кодировку в виде списка. Элемент окрестности определяется для каждой работы j £ J. Для указанной работы в текущем списке определяется окно между ближайшим предшественником и последователем. В соседнем списке работа j перемещается на произвольное место внутри выбранного окна. При этом работы, заключенные между старой и новой позициями работы j перемещаются циклически.

Поиск с запретами Основоположником алгоритма поиска с запретами (Tabu search) является Ф. Гловер, который предложил принципиально новую схему локального поиска [46]. Она позволяет алгоритму не останавливаться в точке локального оптимума, как это предписано в стандартном алгоритме локального спуска, а переходить от одного локального оптимума к другому с целью найти среди них глобальный оптимум. Основным механизмом, позволяющим алгоритму выбираться из локального оптимума, является список запретов. Он строится по предыстории поиска, то есть по нескольким последним решениям 5fc, Sk-u., Sk-h+u и запрещает часть окрестности текущего решения N(Sk)- Точнее на каждом шаге алгоритма очередное решение Sk+i является оптимальным решением подзадачи f(Sk+1) = min{/(5) | j 6 N(Sk) \ Tabuh(Sk)}, где f(S) — значение целевой функции решения S. Множество Tabuh(Sk) С N(Sk) определяется по предшествующим решениям. Список запретов учитывает специфику задачи и, как правило, запрещает использование тех "фрагментов" решения, которые менялись на последних h шагах алгоритма. Константа h > 0 определяет его память. При "короткой памяти" (h = 0) получаем стандартный локальный спуск.

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

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

Генетический алгоритм Идея генетических алгоритмов заимствована у живой природы и состоит в моделировании эволюционного процесса, конечной целью которого является получение оптимального решения сложной комбинаторной задачи. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее. Стандартный генетический алгоритм начинает свою работу с формирования начальной популяции POPq = {Si, S2, -. ■, Sk} — конечного набора допустимых решений задачи. Эти решения могут быть выбраны как случайным образом так и с помощью приближенных алгоритмов, например вероятностных жадных. На каждом шаге эволюции с помощью вероятностного оператора селекции выбираются два решения, родители Si, Sj. Оператор скрещивания по решениям Si,Sj строит новое решение 5', которое затем подвергается небольшим случайным модификациям, которые принято называть мутациями. Затем решение добавляется в популяцию, а решение с наихудшим значением целевой функции удаляется из популяции.

В работе [50] было предложено три варианта генетического алгоритма, использующие соответственно кодировки в виде списка, вектора значений приоритета и вектора приоритетных правил. Во всех трех использовалась последовательная ДП, а также три оператора скрещивания: одноточечный, двуточечный и равномерный. Результаты экспериментов показали, что алгоритм проявляет себя наилучшим образом с использованием двуточечного оператора скрещивания и кодировки списком. В работе [51] этот алгоритм был модернизирован путем введения чередования последовательно декодера с параллельным, а также фазы локального поиска.

Муравьиные колонии Алгоритм муравьиной колонии (МК) возник при моделировании поведения муравьев [37]. Известно, что муравьи фактически не имеют зрения, но способны каким-то образом находить кратчайший путь от источника пищи до муравейника. Двигаясь по местности, они оставляют за собой след в виде сильно пахнущего вещества - феромона. Именно запах позволяет муравьям ориентироваться на местности. При выборе направления с большей вероятностью выбирается направление с более сильным запахом., Основная идея алгоритма МК состоит в реализации принципа коллективного разума. Для поиска экстремума целевой функции алгоритм использует параллельно несколько агентов (искусственных муравьев), которые в ходе поиска накапливают статистическую информацию. Эта информация аккумулируется в общедоступном банке данных и используется агентами независимо друг от друга. Каждый агент действует по правилам вероятностного алгоритма и при выборе направления ориентируется не только на приращение целевой функции, но и на статистическую информацию, отражающую предысторию коллективного поиска.

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

В работе [74] предлагается алгоритм муравьиной колонии для ЗКПОР. Решение представляется в виде списка, а в качестве декодера используется последовательная процедура. На первой итерации алгоритм строит набор списков подобно вероятностному жадному алгоритму с приоритетным правилом. После отбора наилучших решений формируется матрица {Tij I h j £ J} частоты попадания работы j на позицию г в наилучших найденных списках. На последующих итерациях эта информация используется при построении новых решений подобно значениям приоритета.

Гибридные алгоритмы Несколько нестандартный подход к решению задачи предлагается в работе [86]. Рассматривается комбинация переборного алгоритма и локального поиска. На каждой итерации множество переменных (в данном случае работ) делится нар свободных и тг—р фиксированных. После фиксации п—р работ в некотором расписании оставшиеся р работ образуют подпроект размерности р, (р < п). Эта подзадача решается методом полного перебора с заранее установленным временем работы. Если решение найдено менее чем за указанное время Т, то значение параметра р увеличивается. В противном случае его значение уменьшается. 'Затем процесс переходит к следующей итерации.

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

0.4.5 Прочие алгоритмы

Кроме перечисленных существует много других алгоритмов для решения ЗКПОР. В некоторых работах предлагается использовать методы ветвей и границ, в которых число генерируемых расписаний ограничивается полиномом от входных данных или временем работы процедуры [87, 92]. В некоторых алгоритмах вводятся так называемые дополнительные дуги, расширяющие условия предшествования. Основная идея состоит в формировании минимальных по включению множеств работ, не связанных условиями предшествования, но при этом не способных выполняться одновременно из-за ограничений по ресурсам. [18, 23, 91]. Часть алгоритмов основана на решении задачи, сформулированной в терминах целочисленного программирования [88, 78]. В алгоритме [73] используются блочные структуры в расписании. Текущее расписание делится на несколько частей. Затем алгоритм оптимизирует расписание работ внутри каждого блока с целью сократить длину расписания. В работе [76] предлагается алгоритм, основанный на лагранжевой релаксации задачи. Показано, что оптимальному решению релаксированной модели однозначно соответствует оптимальное решение задачи о минимальном разрезе. Вычисление множителей Лагран-жа осуществляется стандартными методами субградиентной оптимизации. В работе также показано, что полученная нижняя оценка совпадает с оценкой линейного программирования.

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

Заключение

1. Гимади Э. X., Залюбовский В. В., Севастьянов В. Полиномиальная разрешимость задач календарного планирования с ограниченными ресурсами и директивными сроками. / / Дискрет, анализ и ис-след. операций. Сер. 2. 2000. Т. 7, № 1. 9-34.

2. Гимади Э. X., Глебов Н. И. Дискретные экстремальные задачи принятия решений: Учебное пособие / Новосибирский ун-т. 1991.

3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размеш,ения / / Дискрет, анализ и исслед. операций. Сер. 2. 1999. Т. 6, № 1. 12-32.

4. Кочетов Ю. А., Столяр А. А. Алгоритм поиска с запретами для задачи календарного планирования с ограниченными ресурсами / / Сборник тезисов конференции "Дискретный анализ и исследование операций", 2000. 187.

5. Кочетов Ю. А., Столяр А. А. Вероятностный адаптивный поиск для задачи календарного планирования с ограниченными ресурсами / / Сборник тезисов конференции "Дискретный анализ и исследование операций", 2004. 188.

6. Кочетов Ю. А., Столяр А. А. Использование чередующихся окрестностей для приближенного решения задачи календарного планиро-ш i'? # ч S ' ш '} вания с ограниченными ресурсами / / Дискрет, анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 2. 29-55.

7. Кочетов Ю. А., Столяр А. А. Локальный поиск с экспоненциальной окрестностью для задачи календарного планирования с ограниченными ресурсами / / Сборник тезисов конференции "Проблемы оптимизации и экономические приложения", 2003. 98.

8. Столяр А. А. Задача календарного планирования с ограниченными ресурсами: исследование окрестностей для локального поиска / / Труды XII Байкальской международной конференции 2001. Т. 6. 46-50.

9. Столяр А. А. Стратегия связывающих путей для задачи календарного планирования с ограниченными ресурсами / / Сборник тезисов конференции "Дискретный анализ и исследование операций", 2002. 238.

10. Столяр А. А. Эволюционный поиск с запретами для задачи календарного планирования с ограниченными ресурсами / / Сборник те-»• зисов конференции "Математическое программирование и приложения", 2003. 218.

11. Aarts Е. Н. L., Korst J. Н. М., van Laarhoven P. J. М. Simulated annealing / / Local -search in'.combinatorial optimizatiun, Chichester: ' John Wiley & Sons, 1997. P. 91-120. •

12. Ahuja R. K., James O. E., Orhn В., Punnen A. P. A survey of very large- scale neighborhood search techniques / / Discrete Appl. Math. 2002. V. 123, P. 75-102.

13. Aiex R. M., Resende M. G. C , Pardalos P.M., Toraldo G. GRASP with "-•'- path" rehnking-for- the three-index: assignment, problem .//..Techn. rep. AT&T Labs Research, Florham Park, NJ, 07733. 2000.

14. Alcaraz J., Maroto C. A robust genetic algorithm for resource allocation in project scheduhng / / Annalls of Operaions Research, V. 102. 2001. P. 83-109. • ^ <* ' •

15. Alfandari L., Plateau A., ToUa P. A two-phase path-relinking algorithmfor the generalized assignment problem / / Proc. of 4th Metaheuristics International Conference, 2001. P. 175-180.

16. Alvarez-Valdes R., Tamarit J. M. Heuristic algorithms for resource- constrained project scheduling: A review and empirical analysis / / Advances in project scheduling. Amsterdam: Elsevier, 1989. P. 113-134.

17. Alvarez-Valdes R., Tamarit J. M. Algoritmos heuristicos deterministas у aleatorios en secuenciacon de proyectos con recursos limitados / / Questii6. 1989. V. 13. P. 173-191.

18. Baar Т., Brucker P., Knust S. Tabu-search algorithms for the resource- constrained project scheduling problem. Working Paper, Universitat Osnabriick, 1997.

19. Boese K. D., Kahng A. В., Muddu S., A new adaptive multi-start technique for combinatorial global optimizations, Oper. Res. Lett. 16 (2), 1994, 101-114. ш) Л'