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

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

екта.

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

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

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

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

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

172

возможность определения ресурсов на цифровом аналоге сетевого графика с использованием в качестве моделирующей величины ре­ сурсов постоянного напряжения. Здесь М РХи М Р 2 — модели работ сетевого графика. Величины напряжений Ut моделируют количест­ во потребляемых ресурсов при выполнении каждой работы; они подаются на вход сумматора только когда ключи открыты, т. е. когда работа выполняется. В начальный момент все триггеры уста­ новлены в нулевое состояние. При поступлении сигнала на вход модели работы М РХ о начале ее выполнения триггер Тг устанавли­ вается в единичное состояние и открывает ключ Кх. Напряжение Ux через Кх Издается на один из входов сумматора 2 - Если в этот же

Рис. 107

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

t/s = S£/£,

где і — номера работ, выполняемых одновременно.

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

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

173

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

Ѣъ

и_ 1 = 1

где R t — сопротивление, моделирующее количество ресурсов, необ­ ходимых для выполнения і-й работы; п — номер работы сетевого графика. #

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

В исходном состоянии ключи К( открыты и закорачивают со­ противления R;. При этом коэффициент передачи усилителя k равен нулю и напряжение на выходе усилителя также равно нулю.

При выполнении і-й работы ключ Kt закрывается и коэффициент передачи

а на выходе сумматора напряжение будет

т. е. пропорционально количеству потребляемых при выполнении і-й работы ресурсов. При одновременном выполнении нескольких работ (например 1-й, 3-й и і-й) напряжение на выходе сумматора

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

При определении различных видов ресурсов, необходимых для

174

/=і Для регистрации графиков суммарных ресурсов на электронно­

лучевом осциллографе или другом регистрирующем приборе можно использовать падение напряжения на измерительном сопротивле­ нии R0:

175-

Применив преобразователь тока в напряжение на основе операци­ онного усилителя постоянного тока (см. рис. 106, в), можно значи­ тельно уменьшить систематическую погрешность схемы.

Уравнения схемы примут в этом случае следующий вид:

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

Комбинированная модель рис. 106, б может быть использована для определения стоимостных характеристик различных категорий работ сетевого графика. Действительно, если возвратиться к функ­ циональной схеме модели работы рис. 67, то можно отметить, что в различных режимах на полюс «Индикация» появляется единичный сигнал, когда рассматриваемая работа принадлежит или: а) крити­ ческому пути, б) дереву максимальных путей, в) фронту выполня­ емых работ, г) множеству работ критической зоны и т. д.

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

Если проводимости gki схемы рис. 106 установить пропорцио­ нальными стоимостям выполнения соответствующих работ, то в ре­ жиме а) мы получим величины Ik или Ѵк, пропорциональными об­ щей стоимости работ критического пути, в режиме б) — стоимости работ дерева максимальных путей, в режиме г) — стоимости работ критической зоны и т. п. Таким образом, стоимостно-ресурсные бло­ ки могут использоваться как устройства предварительной перера­ ботки информации, работающие совместно с цифровой моделью сетевого графика.

Продолжительность выполнения любой работы зависит от числа ее исполнителей и может меняться в некоторых пределах

di/ Dtj.

176

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

полнителей; t — продолжительность выполнения работы. Количество исполнителей является одной из разновидностей

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

Из (6.15) следует, что если потребовать, чтобы трудоемкость работы изображалась числом импульсов, а продолжительность выполнения — величиной вре­ менной задержки сигнала, то количество исполнителей долж­ но отображаться величиной час­ тоты тактового генератора. Эти рассуждения приводят нас к необходимости использования ряда тактовых генераторов, час­ тоты которых однозначно со­ ответствуют возможным града­ циям числа исполнителей. Фраг­

мент соответствующей цифровой модели работы приведен на рис. 109. В счетчик Сч1теперь необходимо записывать трудоемкость выполнения работы. На входе счетчиков включен ряд схем Их— Ик, количество которых равно числу возможных градаций исполните­ лей. Схемы трехвходовые. Первые входы всех схем объединены и подключены к единичному выходу триггера Т1 модели работы. Ко вторым входам подключены генераторы тактовых частот, соот­ ветствующих возможным градациям числа исполнителей. Третьи входы схем И подключены к выходам сдвигового регистра, в который