Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

стояние. За это время в счетчик измерения поступило число импуль­ сов, пропорциональное длине максимального пути от начала графи­ ка до начала данной работы. А это в свою очередь является наиболее ранним сроком начала указанной работы.

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

Определение наиболее поздних допустимых сроков начала работы, ее окончания и полного резерва времени целесообразно проводить

графика нГ

Рис. 74

методом фиктивной работы. При этом в качестве такой дополнитель­ ной работы выбирается линия задержки, длина которой равна длине критического пути (см. рис. 69).

Определение поздних допустимых сроков начала и окончания ра­ боты и резерв времени можно осуществить двумя способами [87]. Один из них предусматривает нахождение этих характеристик за один цикл просчета графика. Однако при таком способе необходимо усложнить счетчик измерения с целью восстановления величины критического пути.

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

121

нальной схеме рис. 74. Для этого предварительно из запоминающих элементов счетчика измерения в счетные элементы заносится вели­ чина критического пути. Начало работы і отрывается от события і, из которого данная работа выходит, и подключается к единичному выходу триггера Т2 (см. рис. 74). В режимах определения поздних характеристик работ и их резервов времени счетчик измерения ставится в режим вычитания. Затем в начальное событие графи­ ка нг подается пусковой импульс, который устанавливает входные триггеры моделей работ Твх в единичное состояние. При этом с единичного выхода триггера поступает разрешающий потенциал на схему совпадения Я. Импульсы от генератора Г И поступают в счетчик модели работы.

Одновременно пусковой импульс переводит триггер Тхв единич­ ное состояние, импульсы от генератора ГИ поступают в линию задержки ЛЗ. После того как в схему поступит число импульсов, пропорциональное длине критического пути, цифровой аналог будет находиться в таком состоянии, что все работы, не связанные с окончанием і-й работы, будут выполнены. На их выходы поступа­ ют сигналы о завершении. Те же работы, которые связаны с і-й работой, не получают сигнала о начале выполнения и не будут вы­ полнены. После поступления в ЛЗ числа импульсов, пропорциональ­ ного длине критического пути, на ее выходе появится сигнал. Этот сигнал устанавливает триггер Т2в единичное состояние. С единичного выхода Г2 сигнал поступает на начало (точка і) і-й работы и на схему совпадения Я2. При этом в счетчик і-й модели работы и в счетчик измерения начинают поступать импульсы от ГИ. После появления импульса в конечном событии графика Кг этот импульс переводит триггеры Тх и Т 2в нулевые состояния и в счетчик измерения прекра­ щается поступление импульсов от ГИ. При таком просчете длина

завершается і-я работа, до конца графика. Иными словами, полу­ ченный путь длиннее критического пути сетевого графика и явля­ ется новым критическим путем.

В счетчике измерения после прекращения поступления импуль­ сов оказывается записанным число импульсов

^ = Г р Іц ^ /к гп а х -

Эта величина, как видно из формулы (1.26), и является величиной наиболее позднего срока начала работы.

Наиболее поздний допустимый срок окончания работы можно определить по схеме рис. 75. При этом предварительно, как и при определении наиболее позднего срока начала работы, из запоминаю­ щих элементов счетчика измерения в счетные элементы заносится величина критического пути. Начало выбранной работы (і, /) отры­ вается от события і, из которого данная работа выходит, и подклю­

122

чается к единичному выходу триггера Т 3 (см. рис. 75). Затем в началь­ ное событие графика нг подается запускающий импульс. Этим импульсом триггер Твх моделей работ устанавливается в единичное состояние, с единичных выходов которых выдается разрешающий потенциал на схему совпадения И. Импульсы от ГИ поступают в счетчики моделей работ, выходящих из начального события графика нг. Одновременно пусковой импульс устанавливает триггер Т1 в единичное состояние и импульсы от ГИ через схему совпадения И1 поступают в линию задержки ЛЗ, которая при определении этой

Рис. 75

временной характеристики устанавливается продолжительностью, равной длине критического пути tKp. В момент появления импульса на выходе линии задержки цифровой аналог будет находиться в таком же состоянии, как и при определении t„.H(ij).

Импульс, появившийся на выходе ЛЗ, устанавливает триггер Т3 в единичное состояние. Сигнал с выхода Т3 устанавливает вход­ ной триггер Тех модели работы (i, j) в единичное состояние и ее счетчик отсчитывает число импульсов, пропорциональное ее про­ должительности. Сигнал о завершении работы (і, /), появившийся в точке / модели работы, устанавливает триггер Т2 в единичное состояние. При этом разрешается поступление импульсов от ГИ через Их и # 2 в счетчик измерения Сч. Импульс, появившийся в конечном событии графика Кг, переводит 7\ и Т2 в нулевые состоя­ ния и при этом прекращается поступление импульсов в счетчик измерения.

123

а эта величина, согласно формуле (1.25), и является, наиболее поздним допустимым сроком окончания работы.

Наиболее поздний срок окончания работы (і, /) есть одновре­ менно и наиболее поздним допустимым сроком свершения события /, в которое данная работа входит. Поэтому для определения этой характеристики событий сетевого графика достаточно определить наиболее допустимые сроки окончания для одной из работ, входящих в каждое событие.

Полный резерв времени для каждой работы можно найти соглас­ но функциональной схеме рис. 76.

ерадіика

Рис. 76

Предварительно, как указывалось ранее, необходимо занести в счетчик измерения величину критического пути. Начало выбранной работы (і, ;') отрывается от события і и подключается к единичному выходу триггера Т2, а точка і', соединяющаяся с событием, под­ ключается к нулевому входу триггера Г8 и к единичному входу триггера Т 3. При поступлении пускового импульса в начальное со­ бытие графика нг и на единичные входы триггеров 7\ и Т2в модели работ, счетчик измерения и в линию задержки ЛЗ начинают посту­ пать импульсы от ГИ. Импульс, появившейся в точке і' модели ра­ боты (£, /), переводит триггер Т2 в нулевое состояние и прекращает через схему совпадения И2 подачу импульсов в счетчике измерения Сч. При этом в счетчике измерения оказывается число импульсов

£сч = 4р £нгі'шах>

где t„ri>щах — длина максимального пути от начала графика до

начала работы (і, /), а эта величина есть наиболее ранний срок нача­ ла данной работы, т. е. из длины критического пути произошло вычитание раннего начала работы (і, /).

Импульс с выхода линии задержки устанавливает триггеры Т2 и Т3 в единичное состояние и разрешает поступление импульсов в

124

модель работы (і, /) через триггер Т 3 и в счетчик измерения. После появления импульса в конечном событии в счетчике измерения оказывается записанным число импульсов

^Сч : ^кр ^НрГтах — ^lj ^/кгтах-

Эта величина, как видно из выражения (1.27), и есть полный резерв времени работы (і , /).

Кроме указанного способа определения поздних допустимых характеристик работ и их резервов времени, в котором используется

имущества обоих способов.

При использовании первого способа необходимо иметь достаточ­ но сложный счетчик измерения. Однако при таком способе опреде­ ления поздних временных характеристик и резервов времени это осуществляется за один цикл. Время, необходимое для этого, в самом неблагоприятном случае (когда производится измерение для работы, лежащей на критическом пути и выходящей из начального события графика) равно 2tKp.

При втором способе нет надобности в сложном счетчике изме­ рения, однако время определения временных характеристик в том же неблагоприятном случае составляет 3fKp-

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

125

образом. На горизонтальную ось наносится равномерная шкала времени t. Каждая работа изображается полоской, располагаемой параллельно оси времени. Длина полоски изображает продолжи­ тельность выполнения работы. Полоска располагается между собы­ тиями і и /, соединенными работой (і, /).

При помощи линейной диаграммы можно просто определить временные характеристики сетевого графика и совокупность работ, выполняемых одновременно. Совокупность работ, которые, по се­ тевому графику можно выполнить одновременно, называется фрон­ том работ F {f). Таким образом, фронту работ могут принадлежать

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

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

Всчетчик Сч заносится число импульсов

ЛГ - / ф . Р ,

126