Яо A(D-xB)

Совместное применение этих приемов оказалось исключительно эффективным. Так, для системы Но/Но/Ъ с коэффициентом загрузки р - 0.9 и коэффициентами вариации исходных распределений vj\, = 0.4 и VB - 3 (данные, близкие к наихудшим из проверенных в смысле сходимости) при начальной норме невязки 19.280 в трех последовательных итерациях были получены невязки 3.350, 2.30- 10 * и 7.23- 10 * . Заметим, что исходный вариант метода для снижения нормы невязки до 10 потребовал 266 шагов, из которых 104 пришлось на последний порядок. Ни в одном из полусотни обсчитаннных случаев не потребовалось более четырех шагов итераций.

3.15. Сети обслуживания

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

и является линейным относительно поправочной матрицы А . Коэффициенты развернутой формы системы уравнений (3.14.22) могут быть выражены через элементы известных матриц А, В и D, после чего она решается стандартным методом. Размер системы может оказаться весьма внушительным (для модели Н/Н-у! - 144 неизвестных), что предъявляет значительные требования к оперативной памяти и делает трудоемким каждый шаг итерации. Однако число итераций резко сокращается.

Дальнейшее уменьшение числа итераций достигается получением лучшего начального приближения. В этих целях перепишем уравнение (3.14.20) в форме xRB - RD-\- А - О . Теперь ясно, что можно принять

3.15. Сети обслуживания 105

ЗЛ5Л. Определения и допущения

Сеть обслуживания состоит из рабочих узлов, занумерованных от 1 до М , источника (узел О ) и стока (узел М--1 ). Новая заявка рождается в источнике; с попаданием заявки в сток фиксируется окончание ее п -сбывания в сети. Если суммарная интенсивность входящего потока не зависит от количества находящихся в сети заявок, сеть считается открытой, в противном случае - зсимкнутой. Практически исследован единственный частный случай замкнутых сетей - сеть с постоянной популяцией (числом заявок) К . Здесь вместо каждой попавшей в сток заявки в источнике мгновенно генерируется (и передается в один из рабочих узлов) новая Замкнутые сети этого вида хорошо моделируют локальные вычислительнь(е системы коллективного пользования. При наличии в сети неоднородных заявок она может быть замкнутой по одним типам и разомкнутой по другим. Такая сеть считается смешаниой.

Маршрут заявки в сети, вообще говоря, случаен и определяется неразложимой матрицей передач R = {fij}: = О, Л/ -h 1 , образо-

ванной вероятностями перехода из /-го в j-й узел. Эти вероятности не зависят от маршрута, уже пройденного заявкой. Неразложимость (неприводимость) сети означает невозможность ее разделения на не связанные допустимыми переходами компоненты.

Для каждого j-гс узла задаются моменты распределения чистой длительности обслуживания {6/), / = 1,1, число каналов rij и дисциплина обслуживания

При наличии заявок нескольких типов / = 1,Q они разбиваются на классы замкнутых Qc и открытых . э всем перечисленным выше величинам приписывается дополнительный (верхний) индекс типа заявки д .

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

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

вероятности {r,j} перехода заявки из узла i в узел j не зависят от предыстории заявки (в частности, от кратности прохождения узла) и от состояния узла-преемника j ;

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

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

В качестве показателей работы сетей обслуживания используют:

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

распределение времени пребывания заявки в сети и его моменты (дифференцированно по видам заявок);

производительность сети (интенсивность потока обслуженных заявок) - только по замкнутым типам.

Строго говоря, независимый расчет узлов возможен только для мультипликативных сетей (П-сетей), для которых совместное распределение вероятностей состояний узлов представим© произведением частных распределений на нормирующий множитель. Соответствующие условия сформулированы в известной теореме ВСМР [108].

Тридцатилетнее развитие методов строгой декомпозиции сетей обслуживания практически исчерпало их возможности. Ряд особенностей реальных задач (узлы типа FCFS с немарковским обслуживанием, с различными распределениями обслуживания для заявок разных видов, с приоритетным обслуживанием) исключает возможность П-решения. Как будет показано в главе 9, характеристики работы СМО сильно зависят от вариации распределений, неучет которой дает намного большие ошибки, чем силовая декомпозиция сети. Кроме того, классические методы расчета сетей имеют слишком быстрый рост трудоемкости при увеличении размерности задачи (в особенности по объему популяции и числу типов заявок) и во многих случаях вынуждают ограничиться средними характеристиками, недостаточными для большинства приложений.