Классификация методов решения задач теории расписаний

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

  • — в виде задач линейного и нелинейного целочисленного программирования (ЛЦП и НЦП);
  • — в виде задач комбинаторной оптимизации с перестановочными расписаниями;
  • — в виде сетевых моделей;
  • — в виде задач параллельного программирования.

На рис. 7.9—7.12 представлена краткая классификация методов решения задач в каждом из способов их формализации.

Методы решения задач ЛЦП и НЦП

Рис. 7.9. Методы решения задач ЛЦП и НЦП

Методы решения задач в виде смешанных графов

Рис. 7.10. Методы решения задач в виде смешанных графов

Методы решения задач параллельного программирования

Рис. 7.11. Методы решения задач параллельного программирования

Методы решения задач комбинаторной оптимизации

Рис. 7.12. Методы решения задач комбинаторной оптимизации

Общая постановка задач комбинаторной оптимизации и методы их решения

Формально многие задачи теории расписаний имеют следующую математическую формулировку:

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

Ниже рассмотрим некоторые универсальные методы решения этой задачи.

Метод ветвей и границ

Пусть ак — множество перестановок при закреплении к новых продуктов:

В методе ветвей и границ (В. и Г.) предполагается наличие некоторой функции, оценивающей значение нижней границы значения критерия для любого подмножества к,(к = 1 ,п):/inf (с^).

Следовательно:

Оценочная функция обладает следующими свойствами:

Определяем рекордное значение:

Тогда метод ветвей и границ включает две фазы:

1 — прямой ход, нацеленный на определение рекордного значения Record по формуле (7.38);

2 — обратный ход, при котором производятся: перерасчет Record; отсечение ненужных ветвей; выбор глобального оптимального решения.

Пример 7.8

Необходимо решить задачу выбора оптимальной стратегии перестановок для пяти продуктов (п = 5) с данными, представленными в виде матрицы [0] (табл. 7.8).

С учетом особенностей этой задачи, для задачи коммивояжера справедливы следующие свойства:

Свойство 1. Решение задачи коммивояжера не изменится, если каждое значение 0,-,- в i-й строке уменьшить на одно и тоже число А,-.

Свойство 2. Решение задачи коммивояжера не изменится, если каждое значение 0,-, в;-ом столбце уменьшить на одно и тоже число б,.

Свойство 3. Используя эти два свойства, можно получить преобразованную матрицу©: Д, = min0y (i = 0,n),8j =min(0y-Л,)() = 0,п), следовательно:

и можно выбрать оценочную функцию для подмножеств ак = {0, iv i2,..., ik,...} в виде

где ак+1 =< ok j >;;gM(CTfc) = {i1,i2,...,ifc}H/inf(a0) = /inf(0) = 0.

Для оптимального решения:

Согласно свойствам 1, 2, 3: где Д0 = Д5 = 2, А-1Л = 4, Д2 = 5, Д3 = 6,

Преобразованная матрица 0 приведена в табл. 7.9.

Таблица 7.8

Матрица затрат 0

0

1

2

3

4

5

0

7

4

7

8

2

1

6

7

6

4

8

2

5

8

6

7

5

3

8

7

6

7

6

4

7

4

8

6

8

5

2

7

7

7

7

Таблица 7.9

Преобразованная матрица затрат 0

0

1

2

3

4

5

0

5

2

4

5

0

1

2

3

1

0

4

2

0

3

0

2

0

3

2

1

0

1

0

4

3

0

4

1

4

5

0

5

5

4

5

На рис. 7.13 приведено дерево вариантов при решении задачи коммивояжера методом ветвей и границ.

Оптимальной последовательностью выпуска продуктов будет п = {0, 2 ,4, 1, 3, 5} и значение критерия оптимизации F(n*) = 29.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >