АМСОИ (10) - Лекция №2 - Методика разработки формализованных схем

Задача для примера

Имеется мастерская по обслуживанию серверов.

Поток клиентов составляет $\lambda$ клиентов/час.

Убыток от клиентов в очереди составляет $S = 15$ долларов/клиентов в час

Есть возможность нанять сотрудников $C_1$ или $C_2$.

$C_1$ обслуживает $\mu_1 = 3$ клиента в час, требует денег $S_1 = 6$ долларов/час.

$C_2$ обслуживает $\mu_2 = 4$ клиента в час, требует денег $S_2 = 10$ долларов/час.

Задача руководителя: оптимизировать работу мастерской.

Считается, что поток клиентов подчиняется закону Пуассона, а обслуживание клиентов - экспоненциальному.

Для оценки эффективности работы фирмы следует использовать следующие выражение, показывающие убытки фирмы:

$S_{\sum} = n_i\cdot S_i + S\cdot Q$ $S$ - зарплата; $n$ - количество сотрудников $i$-го типа; $S\cdot Q$ - убытки от пребывания клиентов в очереди.

Если работают сотрудники $C_1$ или сотрудники $C_2$, то их работу можно описать в виде работы многоканальной СМО: количество ОА равно количеству сотрудников, а производительность равна работе сотрубников.

Рассмотрим пять вариантов работы:

Исходные данные	Вариант 1 $C_1$	Вариант 2 $C_1 + C_1$	Вариант 3 $C_1 + C_1 + C_1$	Вариант 4 $C_2$	Вариант 5 $C_2 + C_2$
Загрузка аппарата, $\rho = \frac{\lambda}{\mu\cdot C}$, где $С$ - количество ОА	$\rho_1 = 0.667$	$\rho_1 = 0.333$	$\rho_1 = 0.222$	$\rho_1 = 0.5$	$\rho_1 = 0.25$
Тип СМО	M/M/1	M/M/2	M/M/3	M/M/1	M/M/2
Количество заявок в очереди, $Q = \frac{C\cdot\rho^{C+1} }{1 - \rho^C}$	1.333	0.082	0.0075	0.5	0.033
Сумарные потери фирмы, $S_{\sum}$	26	13.25	18.1	17.5	20.5
Ранжирование вариантов по предпочтительности	5	1	3	2	4

Вот и выбрали лучший вариант.

Методика разработки формализованных схем

Включает пять этапов:

1. разработка структурной схемы исследуемой СОИ. Схема включает, как правило, коммутаторы, маршрутизаторы, сервера и рабочие станции и прочее оборудование. Количество запросов в системе равно количеству рабочих станций - они их генерируют, потому на них очередей нет, а есть очереди на канале и сервере;
2. выделение основных компонентов СОИ и схемы их взаимодействия;
3. представление компонентов СОИ в виде СМО;
4. разработка формализованных схем СМО;
5. разработка формализованной схемы исследуемой СОИ.

Если сервер многоядерный или многопроцессорный, то его можно представить в виде многоканального ОА.

Анализ разомкнутых СМО с обратной связью

$P$ - вероятность повторного поступления заявки на обслуживание.

$\lambda = \lambda + \lambda_{вх}\cdot P$

$\lambda = \lambda_{вх}\cdot (1 - P)$

$\alpha = \frac{1}{1-P}$ - среднее количество проходов заявки через ОА за время пребывания этой заявки в СМО.

$\lambda_{вх} = \frac{\lambda}{1 - P} = \alpha\cdot\lambda$

Основные формулы для расчёта рассматриваемой системы:

• загрузка ОА: $\rho = \frac{\lambda_{вх} }{\mu} = \frac{\alpha\cdot\lambda}{\mu} = \alpha\cdot\frac{\lambda}{\mu}$;
• количество заявок в очереди: $Q = \frac{\rho^2}{1 - \rho}$;
• количество заявок в системе: $L = Q + \rho = \frac{\rho}{1 - \rho}$;
• определяем времена:
  • $W = \frac{Q}{\lambda_{вх} }$;
  • $T = \frac{L}{\lambda_{вх} }$.

$W_{\sum} = \alpha\cdot W$

$T_{\sum} = \alpha\cdot T$

Если в процессе анализа окажется, что $\rho = \alpha\cdot\frac{\lambda}{\mu}\ge 1$, то значит где-то ошибка, потому что может быть только $\rho < 1$. Тогда надо уменьшать вероятность, или повышать производительность, или ставить дополнительные ОА.

Пример

Исходные данные:

• $\lambda = 4$;
• $\mu = 10$;
• $P = 0.5$.

$\alpha = \frac{1}{1 - P} = 2$

$\rho = 2\cdot\frac{4}{10} = 0.8$

$Q = \frac{0.8^2}{0.2} = 3.2$

$L = \frac{0.8}{0.2} = 4$

$W_{\sum} = \frac{3.2}{4} = 0.8$

$T_{\sum} = \frac{4}{4} = 1$

Домашнее задание №2

Сравнительный анализ времени пребывания заявок в одноканальной и двухканальной СМО.

Построить график зависимости по трём значениям загруженности: 0.1, 0.5 и 0.9.

M/M/1 - $T_1$.

M/M/2 - $T_2$.

$\Delta T = \frac{T_2 - T_1}{T_1}$

$\mu_1 = 2\cdot\mu_2$.

Ищем $\Delta T$:

$\Delta T_{\rho_1} = 0.82$

$\Delta T_{\rho_2} = 0.33$

$\Delta T_{\rho_3} = 0.05$

График: