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

Рис. 5.32

Рис. 5.32 помогает увидеть, что в графике, отображенном на рисунке, можно деталь i на первом станке начать обрабатывать непосредственно после детали j, «подвинув» деталь j (вместе с операциями, которые занимали прежде место между i и j) влево на отрезок, равный продолжительности выполнения первой операции i. Такое преобразование графика допустимо, так как сдвиг первых операций влево может только уменьшить сроки начала выполнения вторых операций. Благодаря этому, время окончания выполнения всех операций также может только уменьшиться, а вместе с ним и срок окончания обработки всех деталей.

Итак, мы можем считать, что в оптимальном решении порядок обработки деталей на первом станке и на втором один и тот же и задается перестановкой

Σп = i1,i2,.....,in (5.66)

Рассмотрим некоторый фрагмент графика σk= i1, i2,..., іk , k < п. Введем обозначение: A(σk)— время окончания выполнения обработки деталей графика σk первым станком, В(σk) - вторым станком.

Очевидно, что

(5.67)

где σk+1= σk, i (рис. 5.33). Критерий оптимальности, следовательно, — минимизация В(σп)

.

Рис. 5.33

Пусть теперь

σ1п = i1,..., іk, i, j,.....,in

- некоторое решение. Построим

σ 2п = i1,..., іk, j, i,.....,in

Обозначим

A(σk) = τ, В(σk)= τ + ∆.

Тогда в σ1п

далее,

или

(5.68)

Аналогично для σ 2п

Нетрудно сообразить, что если

(5.69)

это первое решение лучше второго, так как второй станок высвобождается раньше, следовательно, и В(σ1п) может быть только меньше, чем во втором случае.

Очевидно, неравенство (5.69) эквивалентно следующему:

или

или

(5.70)

Неравенство (5.70) выполняется, если выполняется

(5.71)

Неравенство (5.71) эквивалентно:

(5.72)

Итак, если соотношение (5.72) имеет место, то i j (i предшествует j) в σn. Нетрудно обнаружить, что (5.72) выполняется, если

а) aі≤bi, aj≤bj аі≤аj;

б) aі≤bi, aj>bj; (5.73)

в) aі≥bi, aj≥bj, aj>bі.

Последнее утверждение эквивалентно следующему.

Утверждение (решающее правило). Пусть имеется k таких i, что aі≤bi .

Тогда, если aіl≤bil для l≤ k и, кроме того, aіl≤ ai, j+1 при l < k; aіl > bіl для l> k и, кроме того, bіl ≥ bi, j+1 при l > k, тo

(5.74)

оптимально.

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

Алгоритм, который представлено на рис. 5.34, воплощает процедурно приведенное решающее правило, а рис. 5.35 демонстрирует оптимальное решение (4, 2, 6, 3, 5, 1) нашего примера.

Рис. 5.34

Рис. 5.35

4. Интервалы очередности. Если в задаче одного станка φi( )=αi2, то применение перестановочного приема приведет нас к сравнению двух функций от τ:

(5.75)

Сравнение (5.76) эквивалентно выяснению знака следующего выражения:

(5.76)

Если

то

Если αjTi — αіTj ≠ 0, то определим

(5.77)

Теперь из (5.77) следует, что (пусть )

(5.78)

Там, где τ0іj≤0 или τ0іj ≥ Ti, можно заранее установить согласно (5.78) i j или j i. Если τ0іj попадает в интервал (0, Ti), вопрос i j или j i решается по-другому.

Общая схема решения в таком случае — построение порфириана. В операции ветвления конкретно определяется в зависимости от (σk), какие продолжения σk+2 = σk, i, j согласно (5.78) могут быть разрешены, какие запрещены.

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

В табл. 5.13 операции перенумерованы в порядке убывания .

Таблица 5.13

Вычислим по формуле (5.77) значение τij и результаты вычислений представим в табл. 5.14, где в клетках (i, j) указаны соответствующие интервалы очередности: в этих интервалах [a, b) i j , если только а≤τ<b.

Так, для i = 1, j = 2 по формуле (5.73) имеем

Таблица 5.14

Таким образом, 1 2 для всех τ≥1/2, что и отмечено в табл. 5.14 в клетке (1, 2) интервалом очередности [1/2, ∞).

Отсюда следует, что 2 1 для всех τ при - ∞< τ <1/2, что и отмечено в клетке (2, 1) интервалом очередности [0, 1/2) (так как в наших условиях τ ≥0).

Для і = 1, j= 4 вычисление по формуле (4.101) дают

τ 014 = — (5/6) < 0. Отсюда 1 4 при всех τ ≥ 0, так что 4 1 не может ни при каком интересующем нас τ.

Построение порфириана приведет нас к трем возможным решениям:

2, 1, 3, 4, 5 ,

3, 1, 2, 4, 5 , (5.79)

3, 2, 1, 4, 5 .

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

σп = 2, 1, 3, 4, 5 , F(σп) = 35.

Микромодуль16.

Индивидуальные тестовые задачи

Упражнение 1. Составьте временнỳю диаграмму выполнения работ для сетевого графика, представленного на рис. 5.15 и рис. 5.16, исходя из целей подготовки вечера в кратчайший срок. Можно ли сдвинуть во времени (передвинуть вправо на один день отрезок во временнòй диаграмме) работу 12? 14? Насколько можно сдвигать сроки выполнения работ, лежащих и не лежащих на критическом пути?