Свойство при применении правила СК.
Доказательство. Заметим, что если бы все операции фронта F(t) получили максимальное количество ресурса в интервале длительности Д, то их минимальные продолжительности уменьшились бы на Д, и полные резервы времени остались бы без изменения.
Однако, в силу правила СК, ресурсы в первую очередь получают критические операции. Поэтому уменьшение минимальных продолжительностей критических операций всегда не меньше, чемвсех остальных операций фронта. Поэтому полный резерв любой операции не увеличивается. Отсюда, в частности, следует, что критические операции остаются всегда критическими.
Опираясь на это свойство, докажем оптимальность правил СК для случая независимых операций.
Теорема 2. В случае независимых операций правило СК всегда дает оптимальное решение.
Доказательство. Рассмотрим пример графика использования ресурсов, изображенного на рис. 2.4. Момент завершения комплекса определяется моментом завершения критических операций. |u(t) N(t) t
—> 1. a b Т
Рис. 2.4.
В силу правила СК и доказанного выше свойства, эти операции в любой момент времени имеют приоритет в получении ресурсов перед всеми другими операциями. Поэтому либо они используют весь ресурс (интервал (a, b) на рисунке), либо они выполняются максимальным количеством ресурса. Очевидно, что выполнить критические операции за время, меньшее чем Т, невозможно.
Рассмотрим теперь комплекс операций, который состоит из m независимых путей, каждый из которых, в свою очередь, состоит из ni операций. Обозначим aiJ - максимальное количество ресурсов на j-ой операции i-ой цепочки.
Теорема 3. Если aij > aij+1, j = 1,ni -1, i = 1,m, то правило СК
всегда дает оптимальное решение.
Доказательство, по сути дела, повторяет доказательство теоремы 2.