Дискретно-непрерывная математика (стр. 55 )

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

2. Решение методом последовательного отсеивания вариантов. Рассмотрим пример, заданный табл. 5.21.

Таблица 5.21

Воспользуемся утверждением 1 (правилом доминирования) и построим блок-схему метода отсеивания вариантов для задачи трех станков (рис. 5.43).

Рис. 5.43. Схема решения задачи трех станков последовательным

отсеиванием вариантов.

1. Подготовка таблицы аі, bі , сі к решению. 2. Построение σ1 =і1 , вычисление А (σ1), В (σ1), С (σ1). Образуем P1 — множество (список) всех σ1.

3. k=l. 4. Операция ветвления: каждая σk из Рk порождает σk +1=σk , j , где j не входит в М (σk). 5. Группирование сравнимых σk +1, вычисление В(σk +1) и

С(σk +1). 6. Отбор «лучших» σk +1 согласно правилам доминирования, образование Pk +1 из «лучших» σk +1. 7. k +1 =k. 8. k =п? 9. Рп - решение.

Следующий графический прием упрощает вычисления.

Пусть мы построили

σ3 = 1 , 2, 3

Поставим в соответствие σ3 ее сетевой график и проведем вычисление В(σk) и С(σk) как критических путей в этом сетевом графике. Рис. 5.44 подробно иллюстрирует способ вычислений, впрочем совсем идентичный формулам (5.87). Решение примера представлено таблицей 5.22.

Рис. 5.44. К вычислению А(σk), B(σk), С(σk) в задаче трех станков.

Таблица 5.22

Решение задачи трех станков последовательным отсеиванием вариантов

Таблица 5.22 (продолжение)

Таблица 5.22 (продолжение)

Таблица 5.22 (продолжение)

Замечание. Мы ищем только одно оптимальное решение

3. Решение по схеме «ветвей и границ». Вспомогательная задача для решения задачи трех станков по схеме «ветвей и границ» может быть сформулирована различными способами.

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

Так, если принимать во внимание только времена обработки на третьем станке для всех j, не попавших в M(σk) - обычно это делается тогда, когда вообще

,

не обращая внимания на значения аj и bj (т. е. считая, что аj =bj= 0), то мы получим совершенно тривиально решаемую вспомогательную задачу (рис. 5.45):

(5.93)

Знак (σk) здесь следует понимать как то, что сумма длительностей сj считается только по тем j, которые не входят в М (σk).

Совсем аналогично можно считать существенным только продолжительности вторых операций - особенно если

В этом случае прогноз-обещание можно вычислять по формуле

(5.94)

Здесь знак ( σk) означает, что минимум выбирается среди сj, которые не входят в M(σk).

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

и

- можно получить прогноз

(5.95)

Рис. 5.45. Схема решения задачи трех станков методом ветвей и

границ.

1. Подготовка информации к решению. 2. Формируем вспомогательные задачи, вычисляем ∆(σ0) — для всего множества возможных решений. 3. Строим всевозможные σ1=і1, F0=∞. 4. Существует σl такой, что ∆(σl)<F0(σп)? 5. Выберем (σl) с наименьшим ∆(σl). Применяем операцию ветвления к нашему σl=σk, т. е. образуем σk+l= σk , j, j не приналежить (σk). 6. l=k. 7. k + l=п?

8. Формируем для вновь построенных σk+l вспомогательные задачи, вычисляем ∆(σk), фиксируем (σk), максимальное из всех ∆(σk) при фиксированном σk. 9. Вычисляем F(σп) для вновь образованных σп, наименьшее F(σп) и σп — запоминаем. 10. Решение закончено, F0 (σп) — экстремум.

Прогнозы, вычисляемые по формулам (5.95), (5.94), (5.93), есть прогнозы со вспомогательными задачами как бы задачами одного станка. Обозначим их соответственно через ∆1, ∆2, ∆3.

Прогнозы-обещания можно подсчитывать, если в качестве вспомогательной решать (п. 5.17, п. 3) задачи двух станков. Так, пренебрегая длительностями выполнения первых операций, можно для всех j, не входящих в М(σk), решить задачу двух станков и вычислить оптимальное значение функции-критерия для такой вспомогательной задачи. Обозначим его B'(bj, сj, σk). Тогда ∆4(σk) = B(σk) + B'(bj, cj, σk) может быть принята за прогноз значений F(σn) при данном σk.

Так, пусть в нашем примере σk = 1, 2, 3 .

Согласно рис. 5.44 B(σk)=8. Упорядочим оптимально детали которые остались, а именно, 4, 5, 6, считая, что они обрабатываются только на втором и третьем станках. Согласно алгоритму, приведенному на рис. 5.34, эти детали надо обрабатывать в порядке убывания продолжительности третьих операций (так как они короче вторых во всех деталях), т. е. в последовательности 5,4,6.

Легко подсчитать по правилам расчета B(σk) для задачи двух станков (формула (5.67), что в нашем случае B'(bj, cj, σk)= 12, т. е. ∆4(σk) = 20 (∆4 в этом случае совпадает с ∆2).

На рис. 5.46 приведено решение примера, заданного табл. 5.21, по схеме «ветвей и границ» на рисунке рядом с σk выписаны ∆1, ∆2, ∆3, ∆4, ∆5, где ∆5 максимум среди ∆1, ∆2, ∆3, ∆4.

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

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

Действительно, пусть заданы детали, которые последовательно обрабатываются на четырех станках, aі, bi, cі, dі — продолжительности обработки детали і на 1, 2, 3, 4 станке.