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

единичное состояние триггера Т3отображает сам факт окончания ра­ боты.

После окончания всех работ сетевого графика на всех полюсах «Вход» и «Выход» будут единичные сигналы, а триггеры Г2 моделей работ, принадлежащих путям максимальной длины из начального события в каждое событие сетевого графика, будут в единичном со­ стоянии. Тем самым определится множество работ, образующих де­ рево максимальных путей. В описанном процессе информация о модели работы распространяется слева направо, от полюса «Вход» к полюсу «Выход». Если после окончания этого процесса, который мож­ но назвать вычислительным, так как в нем производилось формиро­ вание временного интервала, пропорционального тому или иному кри­ тическому пути, заземлить один из полюсов «Выход», соответствую­ щий одному из событий сетевого графика, то мы получим процесс, распространяющийся в обратном направлении от полюсов «Выход» к полюсам «Вход». Этот процесс можно назвать индикационным, так как в нем будут выделены модели работ, принадлежащие критиче­ скому пути (путям) из начала графика в то событие, которое мы за­ землили. Убедимся в этом. Пусть рассматриваемая работа входит в событие, которое мы заземлили. Пусть также в это событие вхо­ дит еще несколько работ. По крайней мере одна из них или та, ко­ торую мы рассматриваем, принадлежит искомому критическому пути. Тогда триггер Г2 этой работы находится в единичном состоя­ нии и, поскольку на полюсе «Выход» действует нулевой сигнал, схема Иг будет открыта, ибо на третий ее вход подан разрешающий сигнал У2Это приведет к передаче нулевого сигнала на полюсы «Вход» и «Индикация». К последнему может быть подключен токовый инди­ кационный элемент, который будет сигнализировать о принадлеж­

ности этой работы критическому пути. Нулевой сигнал на полюсе «Вход», соединенном с полюсами «Выход» предшествующих моделей работ, осуществит в них описанные логические операции и так до тех пор, пока мы не придем к начальному событию.

Если одновременно заземлить все события (полюсы «Выход»), то индикационные элементы, подключенные к полюсам «Индикация»! укажут множество работ, принадлежащих дереву максимальных путей из начала графика во все его события; если заземлить только конечное событие — то форму основного критического пути.

Если при проведении вычислительного процесса подать разре­ шающий сигнал на управляющий вход У 3 схемы совпадения # 2, то на ее выходе будет сформирован единичный сигнал в течение промежутка времени от момента, когда 7\ будет установлен в еди­ ничное состояние, до момента, когда будет установлен в единичное положение триггер Т3, т. е. единичный сигнал на выходе # 2, а следовательно нулевой на выходе «Индикация», в данном случае сигнализирует о том, что рассматриваемая работа находится в ста­ дии выполнения. Если в некоторый момент времени остановить вы­ числительный процесс и осуществить индикацию состояния схем И 3, то мы получим информацию о принадлежности работ фронту

116

работ, выполняемых на текущий момент времени. Эта информация может быть использована для построения графиков Ганта и для опре­ деления ресурсных и стоимостных характеристик сетевого графика, к чему мы обратимся подробнее в следующем параграфе.

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

На рис. 29 показана блок-схема определения ранних сроков на­ чала и окончания работ. Вре­ менной интервал, соответствую­ щий измеряемой характеристике, формируется следующим обра­ зом. На полюс «Пуск» посту­ пает сигнал начала отсчета, который устанавливает пусковой триггер Тт в единичное состоя­ ние. Выходной сигнал этого триггера поступает на полюса «Вход» моделей работ, выходя­ щих из начального события, и открывает схему И. Импульсы тактового генератора начинают заполнять измерительный счет­ чик. Через время, соответству­

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

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

117

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

быть выполнены традиционными для цифровой вычислительной тех­ ники методами.

5.4. МЕТОДЫ ОПРЕДЕЛЕНИЯ ВРЕМЕННЫХ ХАРАКТЕРИСТИК ЗАДАЧИ СПУ НА ЦИФРОВОМ АНАЛОГЕ

Одним из основных этапов анализа и расчета сетевых графиков является определение временных характеристик каждой работы.

В цифровых аналогах для определения временных характерис­ тик сетевого графика применяется так называемый метод фиктив­ ной работы, в котором используется вспомагательная модель вет­ ви. Эта модель может включать­ ся в различные точки модели сете­ вого графика. Ее продолжитель­ ность можно изменять в полном диапазоне изменения временных характеристик (от 0 до /кр тах).

Сущность способа заключается в том, что для определения, на­ пример, наиболее позднего срока начала работы (г, j) (рис. 69)

фиктивная работа подключается в начало работы (г, j). Продолжи­ тельность фиктивной работы увеличивается до тех пор, пока работа (i, j) не выйдет на критический путь. Это произойдет тогда, когда продолжительность фиктивной работы будет

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

118

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

Число импульсов между моментом поступления пускового им­ пульса в начальное событие и моментом появления импульса в конечном событии пропорционально длине критического пути.

Наиболее ранний срок начала работы пропорционален числу импульсов между моментом поступления первого импульса в началь­

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

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

Резерв времени для какой-либо работы определяется разностью между числом импульсов, пропорциональных наиболее позднему началу этой работы, или же разностью между числом импульсов, пропорциональных наиболее позднему сроку окончания работы, и числом импульсов, пропорциональных наиболее раннему сроку окончания работы.

Предварительно во все счетчики цифрового аналога сетевого гра­ фика заносится информация о продолжительности работ.

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

Импульс пуска переводит триггер Т из нулевого состояния в единичное. Сигнал его единичного выхода поступает на схему сов­ падения Я, и импульсы от генератора тактовых импульсов (ГИ) одновременно начинают поступать на входы модели работы (МР) и записывающего счетчика Ся. В счетчике Ся записывается число импульсов, пропорциональное длительности ttj работы (£, /).

Полная емкость счетчика записи равна максимальной емкости счетчика модели работы, т. е. равна Nn — числу импульсов.

119

После поступления на вход записывающего счетчика числа импульсов Nn— tu на его выходе появляется импульс переложения. Этот импульс устанавливает триггер Т в нулевое состояние, причем снимается разрешающий сигнал со схемы И и прекращается подача импульсов от Г И в счетчик записи и в счетчик модели работы. В ре­ зультате в счетчик МР оказывается записанным число Nn — /,■/ импульсов, дополняющее количество импульсов, пропорциональных

Здесь прекращается поступление импульсов в счетчик измерения. В этом счетчике оказывается записанным число импульсов, пропор­ циональное длине критического пути.

Наиболее ранний срок начала работы определяется согласно функциональной схеме рис. 72. Импульс пуска устанавливает в единичное состояние входные триггера моделей работ, выходящих из начального события, и триггер Т. При этом импульсы от ГИ по­ ступают в счетчик измерения и в счетчики моделей работ. Импульс появившейся на входе работы і переводит триггер Т в нулевое со­

120