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

V Л хі

Рис. 113

185

довательной схеме за один цикл работы устройства по значениям интеграла в (г — 1)-й точке вычисляется его значение в і-й точке, т. е. последовательная схема приспособлена для выполнения опера­ ций интегрирования при решении задач типа Коши:

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

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

7.3. НЕКОТОРЫЕ ВОПРОСЫ ДИСКРЕТНОГО МОДЕЛИРОВАНИЯ ЗАДАЧ МАССОВОГО ОБСЛУЖИВАНИЯ

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

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

Простейшее допущение для систем с потерями состоит в том, что требования, покидающие систему необслуженными, могут не

186

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

Для систем с ожиданием должен быть установлен порядок об­ служивания. Простейшее допущение состоит в том, что обслужива­ ние производится в порядке поступлений, т. е. по принципу «при­ шел первым — обслужен первым».

Наиболее практическое значение имеет порядок по принципу «пришел последним — обслужен первым». Несмотря на то что та­

щие требования в обслуживающие устройства.

На вход системы поступают требования Рх ч- Рп. В первую оче­ редь требование поступает на ГСИѴ Если ГСИХ свободен, оно об­ служивается, если нет — поступает в следующее обслуживающее устройство. Такое распределение производится с помощью тригге­ ров, входящих в состав ГСП, и схем И — совпадения сигналов

Рис. 115

требования и выхода триггера. Если ГСИ1 свободен, триггер на­ ходится в нулевом состоянии, запрещая прохождение требования на последующие обслуживающие устройства; если ГСП занят, триггер находится в единичном положении, выдавая разрешение на обслуживание поступающего требования следующими устрой­ ствами.

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

187

с помощью регистра со сдвигом импульсов (рис. 115). Частота работы регистра должна превышать частоту следования импульсов и численно быть равна

f — —L.

где Т — период следования импульсов; m — количество обслужи­ вающих устройств. Если ни одно обслуживающее устройство не сво­ бодно, требования покидают систему не обслуженными. В этом случае имеем систему с потерями. Возникает вопрос, сколько посту­ пивших требований обслужено и сколько из них потеряно. На пред-

Р и с . 1 1 6

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

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

В системах с ожиданиями обслуживания может выполняться по принципу «пришел первым — обслужен последним», где при­ оритет отдается не обслуженным требованиям (рис. 117). Не обслу-

188

женные требования заносятся в регистр R. Если сигнал приходит с регистра R± о том, что требований нет, и в то же время приходит сигнал о том, что есть свободные обслуживающие устройства, то с

Рис. 117

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

Рис. 118

Возможны системы, у которых при появлении свободных обслу­ живающих устройств предпочтение отдается необслуженным тре­ бованиям (рис. 118).

189

Если в регистре R 2 нет требований, ожидающих обслуживания, то приходящие на вход системы требования поступают в обслужи­ вающие устройства ГСИ и обслуживаются. Если нет свободных ГСИ, то требование заносится одновременно в регистр R 2. Если ос­ вобождается какой-либо ГСИ и приходит следующее требование, то сигнал о том, что в регистре R 2 есть требования, ожидающие обслуживания, запретит пройти поступившему требованию в об­ служивающее устройство, но разрешит стать в уже существующую

в системе обслуживания поступает на схемы И1 — Ит. Рассматривались системы, у которых время обслуживания оди­

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

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

190

чик регенерации, подключаемый к этому узлу в момент его сверше­ ния?

В общем случае это возможно. Тогда модель узла будет состоять из схемы совпадения Я, счетчика и триггерной схемы Т (рис. 121).

делях узлов используются всего лишь один раз. Возникает возмож­ ность их повторного использования, т. е. возможность переключе­ ния счетчиков из тех узлов, в которых они отрегенерировали, в те, которые свершаются и требуют регенерации. Коммутируемая схема регенерации показана на рис. 121. Обозначим ее через ГСИ (гене­ ратор сигнальных импульсов). Схема управления распределением:

Рис. 122

счетчиков регенерации, подключаемых в свершившийся узел, может, быть следующей (рис. 122). Приходит Р{ требование на подключение в узел ГСИ. Оно выясняет, какой ГСИ в данный момент свободен.. Сигнал поступает на триггер ГСИ. Если триггер в единичном поло­ жении, что соответствует его занятости, то требование через схему

поступает на следующий ГСИ. Если же он свободен, т. е. триггер., в нулевом положении, то последний выдает запрещение на схемы

191,