НАУКА и ОБРАЗОВАНИЕ

Д.И. Батищев, проф. ННГУ (Россия);

Э.Д. Гудман, проф. Мичиганского университета (США);

И.П. Норенков, проф. МГТУ им. Н.Э. Баумана (Россия);

М.Х. Прилуцкий, проф. ННГУ (Россия).

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

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

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

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

·        выбор пары родительских хромосом, при этом вероятность выбора 1-й хромосомы P зависит от значения P_n(r), чем выше пригодность, тем выше вероятность выбора хромосомы 1;

·        кроссовер, заключающийся в разрыве родительских хромосом в случайно выбранной позиции и в образовании хромосом — потомков путем рекомбинации частей хромосом;

·        вычисление значений функции пригодности F(p) для потомков;

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

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

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

·        выбирается работа с наименьшим временем окончания обслуживания на предыдущей стадии;

·        выбирается работа с наименьшим значением директивного срока K_i,

·        выбирается машина, на которой обслуживание данной работы закончится раньше, чем на других машинах;

·        0выбирается машина, на которой обслуживание будет самым дешевым.

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

2.1. Задача 1 (5 работ, 8 машин)

Выполнению подлежат пять работ, каждая из которых состоит из нескольких однотипных операций. Работы 0, 2 и 4 состоят каждая из одной операции, работы 1 и 3 - из двух операций. Все работы выполняются на трех стадиях. На первой стадии находятся три машины 0,1 и 2, на второй стадии - три машины 3, 4 и 5 и на третьей стадии — две машины 6 и 7. В табл. 1 приведено время (в относительных единицах) выполнения работ.

Таблица 1

Все работы разбиваются на три семейства (0, 1 и 2) относительно времени переналадок. В семейство 0 входят работы 0 и 4, в семейство 1 - работы 1 и 3, в семейство 2 — работа 2. В табл. 2 приведено время переналадок машин в зависимости от семейств, к которым принадлежат работы. Контрольные и директивные сроки завершения выполнения работ приведены в табл. 3. Величины штрафов за нарушения контрольных и директивных сроков равны соответственно 2 000 и 10 000 для любой работы.

Расписание r определяется последовательностями выполнения работ на машинах

Оценивается расписание по значению

где F₁(p) — суммарные затраты из-за нарушения сроков выполнения работ; F₂(p) - суммарные затраты на переналадки машин; F₃(p) - суммарные затраты на выполнение работ на машинах.

Лучшим расписанием, полученным с использованием предложенных алгоритмов, является расписание

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

2.2. Задача 2 (105работ, 15машин).

Эта задача является наиболее сложной из серии решенных задач. Множество допустимых решений включает в себя астрономическое число (105!)¹⁵ вариантов.

2.2.1. Решение задачи методом комбинирования эвристик. Хромосома включала 420 генов. Для решения использовались два варианта алгоритмов — однопопуляционный и многопопуляционный, реализованный в программном комплексе GALOPPS [4].

Типичный характер зависимости лучшего достигнутого значения функции пригодности FF (Fitness Function) от числа R оценок FF в процессе эволюции представлен на рисунке, где показано, что после некоторого значения R_B вероятность дальнейшего улучшения FF близка к нулю. Горизонтальный участок можно соотнести с явлением вырождения, когда рекомбинация уже не приводит к возникновению новых хромосом, а получить значения ниже FF_B за счет мутаций крайне маловероятно. Очевидно, что многопопуляционный алгоритм обеспечивает более позднее наступление вырождения при лучших значениях FF_B, однако однопопуляционный алгоритм дает более быстрое снижение FF на начальном участке кривой.

Таблица 2

Таблица 3

В табл. 4 приведены некоторые результаты численных экспериментов, полученные с помощью программы GALOPPS. Использовались восемь популяций, которые обменивались частью своих хромосом с соседями после каждого цикла; цикл при этом состоял из пяти смен поколений; в табл. 4 L_B - число циклов, соответствующее наступлению вырождения. Затраты машинного времени вполне приемлемы для решения практических задач: 1,5-2,0 ч на синтез расписания на ЭВМ Pentium 100 МГц или около 0,2 с на одно вычисление FF в данной задаче.

Таблица 4

Для оценки эффективности метода комбинирования эвристик полезно привести данные (табл. 5), полученные при использовании поочередно какой-либо одной эвристики вместо комбинирования эвристик (штраф за нарушение строгого ограничения принят равным 1000 и за нарушение "мягкого" ограничения - 10). Ни одна из эвристик 1 — 8 в отдельности не позволила получить решения, удовлетворяющего строгим ограничениям задачи. Случайное комбинирование эвристик, т.е. использование метода Монте-Карло вместо генети­ческого алгоритма, дает значения FF не лучше, чем 22300.

Таблица 5

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

Методика формирования H_a основана на выполнении серии расчетов расписания с меняющимся составом эвристик в текущем наборе H_p. Вначале H_p = H_f. Далее рассчитывается FF после удаления из Н_р очередной эвристики. Если при этом FF ухудшилась, то эвристика возвращается в текущий набор, иначе переходим к проверке полезности другой эвристики.

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

Применение методики отбора эвристик в подмножество Н_a позволило заметно улучшить результаты синтеза расписаний. Так, при наборе H_f, состоящем из восьми эвристик, упомянутых в табл. 5, типичные значения FF, полученные при синтезе расписаний с помощью программы GALOPPS после 10-15 циклов, находились в диапазоне 22300 - 22500, а при наборе, включающем только эвристики 1, 7 и 8, получены результаты, приведенные в табл. 4. В то же время при других исходных данных рекомендуемый состав эвристик оказался иным - в него вошли эвристики 1, 6 и 5.

2.2.2. Решение задачи декомпозиционным методом. Решение задачи осуществлялось в двух режимах.

Режим 1. Основная характеристика, оценивающая построенное расписание, - Cost scheduling (стоимость расписания, полученного при соответстующем варианте). Для этого режима задавались Cost penalt (штраф за нарушение "мягкого" срока выполнения работ), равный 1000, и Cost limit (штраф за нарушение "жесткого" срока выполнения работ), равный 10000.

Результаты вычислительного эксперимента для режима 1 приведены в табл. 6.

Таблица 6

В табл. 6 использованы следующие обозначения: Epsilon (h) — управляющий параметр алгоритма, Variant — номер варианта решения задачи, Cost scheduling -стоимость расписания, полученного при соответствующем варианте, Penalty - число нарушенных "мягких" сроков в построенном расписании, Limit - число нарушенных "жестких" сроков в построенном расписании, Time - время (в минутах) решения задачи.

Проведенный эксперимент позволяет сделать вывод о том, что решение задачи перед началом планируемого периода (в начале недели) необходимо проводить при h=6 или h=5, затрачивая на построение расписания от 2 до 2,5 ч. Корректировку расписания в процессе выполнения работ лучше всего проводить при h=3 (время пересчета 1 мин).

Режим 2. Основные характеристики, оценивающие построенное расписание, - Penalty (число нарушенных "мягких" сроков в построенном расписании) и Limit (число нарушенных "жестких" сроков в построенном расписании). Для этого режима задавались Cost penalt (штраф за нарушение "мягкого" срока выполнения работ), равный 8000, и Cost limit (штраф за нарушение "жесткого" срока выполнения работ), равный 32000.

Результаты вычислительного эксперимента для режима 2 приведены в табл. 7. Здесь Cost scheduling (new) - стоимость расписания при значениях Cost penalt=8000, Cost limit=32000; Cost scheduling (old) -стоимость расписания при значениях Cost penalt=1000, Cost limit= 10000. Из табл. 7 следует, что в случае, когда число нарушений сроков выполнения работ является наиболее важным фактором, оценивающим построенное расписание, решение задачи нужно осуществлять, используя второй режим.

Таблица 7

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

Алгоритмы, реализующие метод комбинирования эвристик и ранее предложенный метод декомпозиций, опробованы на ряде многостадийных задач теории расписаний, мощность множества допустимых решений которых оценивается величиной (n!)^m, где (n, m) — исходные параметры, задающие размеры решаемой задачи. Результаты проведенного вычислительного эксперимента позволяют сделать вывод о целесообразности использования предложенных схем к решению сложных, большеразмерных задач дискретной оптимизации.

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

1. Батищев Д.И., Гудман Э.Д., Норенков И.П., Прилуцкий М.Х. Метод декомпозиций для решения комбинаторных задач упорядочения и распределения ресурсов // Информационные технологии. 1997, № 1. С. 29-33.

2. Giffler В., Thompson G.L. Algorithms for solving production-scheduling problems // Operat. Res. (1964), 12, № 2. P. 305-324.

3. Норенков И.П. Комбинированные и генетические алгоритмы составления расписаний в задачах проектирования // Вестник МГТУ им. Н.Э. Баумана, 1995. № 2. С. 36-43.

4. Goodman E.D., Punch W.F. New Techniques to Improve / Coarse-Grain Parallel GA Performance/ - Proc. of CAD-95, Yalta-Gurzuff, P. 7-15.

5. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учеб. пособие. Воронеж, гос. техн. ун-т; Нижегородский гос. ун-т. Воронеж, 1995, 69 с.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, №2. 1997.

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ