Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

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

#12 декабрь 2004

Университета штата Нью-Йорк, адекватным доступом к современным материалам и литературе по соотве тствующей научной проблематик

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

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

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

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

 

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

 

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

 

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

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

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

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

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

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

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

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

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

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

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

·        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

3

4

5

6

7

Номера работ

0

100

120

-

-

220

200

80

110

1

-

100

120

110

-

120

70

60

2

170

-

150

130

100

-

140

100

3

-

140

130

-

50

60

100

100

4

190

200

-

130

-

120

120

130

Стоимость

g

10

20

30

20

10

30

30

20

q

10

30

20

10

30

10

20

10

Примечание. В строке g содержится стоимость (в относительных единицах) единицы времени выполнения любой работы на соответствующей машине: в строке q – затраты на переналадки машин.

 

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

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

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

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

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

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

 

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

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

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

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

Таблица 2

 

Номера машин

0

1

2

3

4

5

6

7

Семейство-1

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

1

2

0

0

10

25

0

10

20

0

20

10

0

10

30

0

30

40

0

10

20

0

30

50

0

30

10

1

20

0

30

20

0

40

30

0

30

40

0

20

30

0

20

30

0

10

40

0

20

10

0

30

2

15

40

0

30

20

0

30

20

0

10

30

0

10

20

0

10

30

0

40

40

0

10

50

0

 

Таблица 3

Сроки работы

Работы

0

1

2

3

4

Контрольные

600

600

700

800

800

Директивные

700

700

800

900

900

 

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

Таблица 4

Размер популяции Z

FF после

5 циклов

10 циклов

LM циклов

27

22236

22159

22090 (LM=36)

31

22121

22097

21967 (LM=29)

35

22177

22089

22084 (LM=12)

39

22242

22145

22107 (LM=19)

47

22149

22070

21986 (LM=27)

55

22221

22153

22080 (LM=25)

73

22169

22122

22108 (LM=12)

 

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

Таблица 5

Номер эвристики

Значение FF

Количество нарушений сроков

К1 -директивных

К2-контрольных

1

43159

14

73

2

47599

17

83

3

83979

52

95

4

66931

31

50

5

34429

5

90

6

31345

2

79

7

103591

68

82

8

104875

71

93

 

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

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

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

Применение методики отбора эвристик в подмножество Нa позволило заметно улучшить результаты синтеза расписаний. Так, при наборе Hf, состоящем из восьми эвристик, упомянутых в табл. 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

Epsilon

h=6

h=5

h=4

h=3

h=2

h=l

Variant

1

2

3

4

5

6

Cost scheduling

21924

22030

22177

22181

22469

24362

Penalty

39

45

41

41

57

27

Limit

0

0

0

0

0

0

Time

150

120

8

1

0.5

0.1

 

В табл. 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

Epsion

h=3

h=2

Variant

1

2

Cost scheduling (new)

22 825

23 288

Cost scheduling (old)

22 195

22 308

Penalty

9

14

Limit

0

0

Time

1

0.5

 

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

Алгоритмы, реализующие метод комбинирования эвристик и ранее предложенный метод декомпозиций, опробованы на ряде многостадийных задач теории расписаний, мощность множества допустимых решений которых оценивается величиной (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.

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

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)