Каталог поддерживаемых моделей СМО

Библиотека Most-Queue поддерживает широкий спектр моделей систем массового обслуживания. Этот каталог содержит описание всех доступных моделей с примерами использования.

FIFO системы (дисциплина First In First Out)

M/M/c

Описание: Многоканальная система с пуассоновским потоком и экспоненциальным обслуживанием.

Класс расчета: MMnrCalc

Пример:

from most_queue.theory.fifo.mmnr import MMnrCalc

calc = MMnrCalc(n=3)  # 3 канала
calc.set_sources(l=2.0)
calc.set_servers(mu=1.0)
results = calc.run()

M/M/c/r

Описание: M/M/c с ограниченной очередью (максимум r мест в очереди).

Класс расчета: MMnrCalc

Пример:

from most_queue.theory.fifo.mmnr import MMnrCalc

calc = MMnrCalc(n=3, r=20)  # 3 канала, очередь до 20
calc.set_sources(l=2.0)
calc.set_servers(mu=1.0)
results = calc.run()

M/G/1

Описание: Одноканальная система с пуассоновским потоком и произвольным распределением времени обслуживания.

Класс расчета: MG1Calc

Пример:

from most_queue.theory.fifo.mg1 import MG1Calc
from most_queue.random.distributions import H2Distribution

calc = MG1Calc()
calc.set_sources(l=0.5)

h2_params = H2Distribution.get_params_by_mean_and_cv(mean=2.0, cv=0.8)
b = H2Distribution.calc_theory_moments(h2_params, 5)
calc.set_servers(b)

results = calc.run()

M/G/1 SRPT

Описание: Одноканальная M/G/1 с дисциплиной Shortest Remaining Processing Time (прерывание по остатку работы). Численно: формула Schrage–Miller (1966).

Класс расчета: MG1SrptCalc
Симуляция: SizeBasedQsSim(discipline="SRPT") — размер заявки сэмплируется при приходе.

Пример:

from most_queue.theory.srpt import MG1SrptCalc
from most_queue.random.distributions import H2Distribution

calc = MG1SrptCalc()
calc.set_sources(1.0)
h2 = H2Distribution.get_params_by_mean_and_cv(0.7, 1.2)
calc.set_servers(h2, "H")
results = calc.run()

M/G/1 SJF (SPT)

Описание: Непрерываемое обслуживание по наименьшему истинному размеру (Shortest Job First / Shortest Processing Time).

Класс расчета: MG1SjfCalc
Симуляция: SizeBasedQsSim(discipline="SJF")

M/G/1 PSJF

Описание: Прерываемое обслуживание по исходному размеру заявки (отличается от SRPT).

Класс расчета: MG1PsjfCalc
Симуляция: SizeBasedQsSim(discipline="PSJF")

M/G/1 SPJF (с предсказаниями)

Описание: Непрерываемое обслуживание по предсказанному размеру (Y) (Mitzenmacher, 2020). Совместное распределение ((X,Y)) задаётся объектом предиктора (PerfectPredictor, ExpNoisePredictor, …).

Класс расчета: MG1SpjfCalc
Симуляция: SizeBasedQsSim(discipline="SPJF") + set_predictor(...).

Пример:

from most_queue.theory.srpt import MG1SpjfCalc
from most_queue.theory.srpt.utils.predictor import ExpNoisePredictor

calc = MG1SpjfCalc()
calc.set_sources(0.5)
calc.set_servers(1.0, "M")
calc.set_predictor(ExpNoisePredictor())
results = calc.run()

GI/M/1

Описание: Одноканальная система с общим потоком поступления и экспоненциальным обслуживанием.

Класс расчета: GIM1Calc

Пример:

from most_queue.theory.fifo.gi_m_1 import GIM1Calc
from most_queue.random.distributions import GammaDistribution

calc = GIM1Calc()

gamma_params = GammaDistribution.get_params_by_mean_and_cv(mean=2.0, cv=0.6)
a = GammaDistribution.calc_theory_moments(gamma_params)
calc.set_sources(a)

calc.set_servers(mu=0.6)
results = calc.run()

GI/M/c

Описание: Многоканальная система с общим потоком поступления и экспоненциальным обслуживанием.

Класс расчета: GiMn

Пример:

from most_queue.theory.fifo.gi_m_n import GiMn
from most_queue.random.distributions import GammaDistribution

calc = GiMn(n=3)  # 3 канала

gamma_params = GammaDistribution.get_params_by_mean_and_cv(mean=2.0, cv=0.6)
a = GammaDistribution.calc_theory_moments(gamma_params)
calc.set_sources(a)

calc.set_servers(mu=0.6)
results = calc.run()

H₂/M/c (метод Такахаси-Таками)

Описание: Многоканальная система с гиперэкспоненциальным потоком поступления (H₂) и экспоненциальным обслуживанием (M). Использует упрощённый алгоритм §7.6.1 (формулы для z_j, x_j, t_{j,i}, уровень 0).

Класс расчета: H2MnCalc

Пример:

from most_queue.theory.fifo.gmc_takahasi import H2MnCalc
from most_queue.random.distributions import H2Distribution

calc = H2MnCalc(n=3)

h2_params = H2Distribution.get_params_by_mean_and_cv(1.0, 1.2, is_clx=True)  # mean, cv
#
# Для CV<1 используйте complex-fit: is_clx=True.
# Важно: симулятор `QsSim` не умеет генерировать H2 с комплексными параметрами,
# поэтому сравнение с симуляцией возможно только когда параметры вещественные.
calc.set_sources(h2_params)

calc.set_servers(b=2.0)  # среднее время обслуживания

results = calc.run()

H₂/H₂/c (метод Такахаси-Таками)

Описание: Многоканальная система с гиперэкспоненциальным потоком поступления и гиперэкспоненциальным обслуживанием. Использует алгоритм §7.6.2 (CH7).

Класс расчета: HkHkNCalc

Пример:

from most_queue.theory.fifo.hkhk_takahasi import HkHkNCalc
from most_queue.random.distributions import H2Distribution

calc = HkHkNCalc(n=3, k=2)

h2_arr = H2Distribution.get_params_by_mean_and_cv(1.0, 1.2)
# Для CV<1 используйте complex-fit: is_clx=True (тогда параметры могут быть комплексными).
calc.set_sources(u=[h2_arr.p1, 1 - h2_arr.p1], lam=[h2_arr.mu1, h2_arr.mu2])

h2_srv = H2Distribution.get_params_by_mean_and_cv(2.0, 1.2)
calc.set_servers(y=[h2_srv.p1, 1 - h2_srv.p1], mu=[h2_srv.mu1, h2_srv.mu2])

results = calc.run()

Примечание про CV<1: при (CV<1) H₂ аппроксимация использует complex-fit (комплексные параметры). Симулятор QsSim не генерирует H₂ с комплексными параметрами, поэтому для валидации удобно сравнивать расчёт (H₂ complex-fit) с симуляцией эквивалентной по mean/CV Gamma-модели (см. тесты tests/test_tt_vs_sim_gamma_cvl1.py).

M/D/c

Описание: Многоканальная система с пуассоновским потоком и детерминированным временем обслуживания.

Класс расчета: MDnCalc

Пример:

from most_queue.theory.fifo.m_d_n import MDnCalc

calc = MDnCalc(n=3)
calc.set_sources(l=2.0)
calc.set_servers(b=1.0)  # постоянное время обслуживания
results = calc.run()

E_k/D/c

Описание: Многоканальная система с распределением Эрланга межприходных времен и детерминированным обслуживанием.

Класс расчета: EkDnCalc

Пример:

from most_queue.theory.fifo.ek_d_n import EkDnCalc

calc = EkDnCalc(n=3, k=2)  # 3 канала, Эрланга порядка 2
calc.set_sources(l=2.0)
calc.set_servers(b=1.0)
results = calc.run()

M/H₂/c (метод Такахаси-Таками)

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

Класс расчета: MGnCalc

Пример:

from most_queue.theory.fifo.mgn_takahasi import MGnCalc
from most_queue.random.distributions import H2Distribution

calc = MGnCalc(n=5)

calc.set_sources(l=2.0)

h2_params = H2Distribution.get_params_by_mean_and_cv(mean=2.0, cv=1.2, is_clx=True)
calc.set_servers(h2_params)

results = calc.run()

Системы с приоритетами

M/G/1/PR (прерываемый приоритет)

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

Класс расчета: MG1Preemptive

Пример:

from most_queue.theory.priority.preemptive.mg1 import MG1Preemptive

calc = MG1Preemptive(num_of_classes=3)
calc.set_sources([0.1, 0.2, 0.3])  # интенсивности для каждого класса

# Моменты времени обслуживания для каждого класса
b = [
    [2.0, 4.0, 8.0],  # класс 1
    [3.0, 9.0, 27.0], # класс 2
    [4.0, 16.0, 64.0] # класс 3
]
calc.set_servers(b)

results = calc.run()

M/G/1/NP (непрерываемый приоритет)

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

Класс расчета: MG1NonPreemptive

Пример:

from most_queue.theory.priority.non_preemptive.mg1 import MG1NonPreemptive

calc = MG1NonPreemptive(num_of_classes=3)
calc.set_sources([0.1, 0.2, 0.3])
calc.set_servers(b)  # моменты для каждого класса
results = calc.run()

M/G/c/PR и M/G/c/NP

Описание: Многоканальные системы с приоритетами (прерываемый и непрерываемый).

Класс расчета: MGnInvarApproximation

Пример:

from most_queue.theory.priority.mgn_invar_approx import MGnInvarApproximation

calc = MGnInvarApproximation(n=5, priority="PR")  # или "NP"
calc.set_sources([0.1, 0.2, 0.3])
calc.set_servers(b)
results = calc.run()

M/Ph/c/PR

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

Класс расчета: MPhNPrtyBusyApprox

Пример: См. тест test_m_ph_n_prty.py

Системы с отпусками (Vacations)

M/H₂/c с прогревом

Описание: Многоканальная система с гиперэкспоненциальным обслуживанием и прогревом каналов.

Класс расчета: MH2H2WarmCalc

Пример:

from most_queue.theory.vacations.m_h2_h2warm import MH2H2WarmCalc

calc = MH2H2WarmCalc(n=3)
# Настройка параметров прогрева и обслуживания
# (см. тест test_m_h2_h2warm.py)

M/G/1 с прогревом

Описание: Одноканальная система с прогревом.

Класс расчета: MG1WarmCalc

M/Ph/c с прогревом, задержкой и отпусками

Описание: Сложная система с H₂-обслуживанием, H₂-прогревом, H₂-задержкой и H₂-отпусками.

Класс расчета: MGnWithH2DelayColdWarm

Пример: См. тест test_mgn_with_h2_delay_cold_warm.py

Системы с отрицательными заявками

M/G/1 RCS (Remove Customer from Service)

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

Класс расчета: MG1RCS

Пример:

from most_queue.theory.negative.mg1_rcs import MG1RCS

calc = MG1RCS()
calc.set_sources(l=0.5, l_neg=0.1)  # l_neg - интенсивность отрицательных заявок
calc.set_servers(b)
results = calc.run()

M/G/c RCS

Описание: Многоканальная система с отрицательными заявками типа RCS.

Класс расчета: MGnRCS

M/G/c Disaster

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

Класс расчета: MGnDisaster

Пример: См. тесты test_mgn_disaster.py и test_mg1_disaster.py

Fork-Join системы

M/M/c Fork-Join

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

Класс расчета: ForkJoinMarkovianCalc

Пример:

from most_queue.theory.fork_join.m_m_n import ForkJoinMarkovianCalc

calc = ForkJoinMarkovianCalc(n=5, k=2)  # 5 каналов, требуется 2
calc.set_sources(l=1.0)
calc.set_servers(mu=1.0)
results = calc.run()

M/G/c Split-Join

Описание: Система Split-Join с произвольным распределением времени обслуживания.

Класс расчета: SplitJoinCalc

Пример: См. тест test_fj_sim.py

Системы с пакетным поступлением

M^x/M/1

Описание: Система, где заявки поступают пакетами случайного размера.

Класс расчета: BatchMM1

Пример:

from most_queue.theory.batch.mm1 import BatchMM1

calc = BatchMM1()
# Вероятности размеров пакетов: [p(1), p(2), p(3), ...]
batch_probs = [0.2, 0.3, 0.1, 0.2, 0.2]
calc.set_sources(l=0.5, batch_probs=batch_probs)
calc.set_servers(mu=1.0)
results = calc.run()

Системы с нетерпеливыми заявками

M/M/1/D (с экспоненциальным нетерпением)

Описание: Система, где заявки могут покинуть очередь, если ожидание слишком долгое.

Класс расчета: MM1Impatience

Пример: См. тест test_impatience.py

Закрытые системы

Engset (M/M/1/N)

Описание: Система с конечным числом источников заявок.

Класс расчета: EngsetCalc

Пример:

from most_queue.theory.closed.engset import EngsetCalc

calc = EngsetCalc()
calc.set_sources(N=10, lambda_source=0.5)  # 10 источников
calc.set_servers(mu=1.0)
results = calc.run()

Сравнительная таблица моделей

Модель	Класс расчета	Симуляция	Приоритеты	Особенности
M/M/c	MMnrCalc	QsSim	-	Базовая модель
M/G/1	MG1Calc	QsSim	-	Произвольное обслуживание
M/G/1 SRPT	MG1SrptCalc	SizeBasedQsSim	-	Size-based, Schrage–Miller
M/G/1 SJF	MG1SjfCalc	SizeBasedQsSim	-	Non-preemptive по размеру
M/G/1 PSJF	MG1PsjfCalc	SizeBasedQsSim	-	Preemptive по исходному размеру
M/G/1 SPJF	MG1SpjfCalc	SizeBasedQsSim	-	По предсказанию Y
GI/M/1	GIM1Calc	QsSim	-	Общий поток
M/G/c/PR	MGnInvarApproximation	PriorityQueueSimulator	Да	Прерываемый приоритет
M/G/c/NP	MGnInvarApproximation	PriorityQueueSimulator	Да	Непрерываемый приоритет
Fork-Join	ForkJoinMarkovianCalc	ForkJoinSim	-	Параллельное обслуживание
M^x/M/1	BatchMM1	QueueingSystemBatchSim	-	Пакетное поступление
Engset	EngsetCalc	QueueingFiniteSourceSim	-	Конечное число источников

Примеры использования

Все модели имеют примеры использования в папке tests/. Рекомендуется изучить соответствующие тесты для понимания деталей использования.

См. также:

Симуляция СМО — имитационное моделирование
Численные методы — аналитические расчеты
Приоритетные системы — детали работы с приоритетами
Сети очередей — моделирование сетей

FilesExpand file tree

models.md

Latest commit

History

models.md

File metadata and controls

Каталог поддерживаемых моделей СМО

FIFO системы (дисциплина First In First Out)

M/M/c

M/M/c/r

M/G/1

M/G/1 SRPT

M/G/1 SJF (SPT)

M/G/1 PSJF

M/G/1 SPJF (с предсказаниями)

GI/M/1

GI/M/c

H₂/M/c (метод Такахаси-Таками)

H₂/H₂/c (метод Такахаси-Таками)

M/D/c

E_k/D/c

M/H₂/c (метод Такахаси-Таками)

Системы с приоритетами

M/G/1/PR (прерываемый приоритет)

M/G/1/NP (непрерываемый приоритет)

M/G/c/PR и M/G/c/NP

M/Ph/c/PR

Системы с отпусками (Vacations)

M/H₂/c с прогревом

M/G/1 с прогревом

M/Ph/c с прогревом, задержкой и отпусками

Системы с отрицательными заявками

M/G/1 RCS (Remove Customer from Service)

M/G/c RCS

M/G/c Disaster

Fork-Join системы

M/M/c Fork-Join

M/G/c Split-Join

Системы с пакетным поступлением

M^x/M/1

Системы с нетерпеливыми заявками

M/M/1/D (с экспоненциальным нетерпением)

Закрытые системы

Engset (M/M/1/N)

Сравнительная таблица моделей

Рекомендации по выбору модели

Примеры использования