Физические основы вычислительных процессов

Рассмотрим теперь случай g = 0 и р = 1. Предположим, что в сети находится К заявок. Цикл обслуживания каждой заявки начинается в узле 1, затем заявка передается на обслуживание в узел 2 и так далее. По окончании обслуживания в узле N происходит возвращение в узел 1, и начинается новый цикл (см. рис.2.11 ).

m₁ m₂ m_N

l₁ l₂ l_N

Узел 1 Узел 2 Узел N

Рис.8.2. Замкнутая сеть с циклическим обслуживанием

Дисциплина очереди в каждом из N узлов - FCFS, ограничений на объем накопителей в узлах нет. Время обслуживания в узле i, i=1,2,...,N, имеет показательный закон распределения с параметром m_i . Таким образом, мы имеем замкнутую марковскую СеМО типа [М|М|1]^N с кольцевой матрицей маршрутизации

0 1 0 0 . . . 0

0 0 1 0 . . . 0

P = 0 0 0 1 . . . 0 .

… ………………

1 0 0 0 . . . …

и уравнениями баланса

m₁x₁ = m_Nx_N,

m_ix_i = m_i-1x_i-1 , i=1,2,...,N,

Полагая х₁= 1, находим решения уравнений баланса:

x_i= m₁ / m_i,

i =1,2, ..., N.

Важной характеристикой замкнутой сети в стационарном режиме является среднее время цикла заявки, т.е. среднее время между двумя последовательными поступлениями данной заявки в узел 1. Обозначим это среднее время через Т_c. Для установившегося режима по формуле Литтла имеем:

Т_c = ,

где l_i - интенсивность поступления заявок в узел 1. С другой сто­роны,

l₁ = m_N[1 – P{Q_N(¥) = 0}] ,

где m_N - интенсивность обслуживания в узле N ; 1 – P{Q_N(¥) = 0} - вероятность того, что в установившемся режиме узел N не пуст. Отсюда находим

.

Вычисляя P{Q_N(¥) = 0} по формуле (2.16) для вероятностей состояний замкнутой СеМО с одноканальными узлами, получаем

,

где A_N = {k: k_i ³ 0, } , A_N-1 = {k: k_i ³ 0, } .

Если в физической системе, моделируемой данной СеМО, имеется возможность изменять интенсивности обслуживания в узлах, причем цена увеличения m_i на единицу равна с_i, и есть ограничение стоимости производимых работ

C(m) = c₁m₁ + c₂m₂ + … + c_Nm_N £ C_max ,

то в этом случае можно решить задачу оптимального выбора интенсивностей обслуживания m=(m₁, m₂, . . . , m_N), при котором средняя продолжительность цикла Т_c обслуживания одной заявки минимальна. В случае N=2 задача может быть решена так же, как в п.8.7.1 ме­тодом множителей Лагранжа . При N >2 эта задача может быть решена численно, методами многомерной оптимизации.

Физические основы вычислительных процессов