16.22: Безперервні ланцюги черги часу

\(\newcommand{\P}{\mathbb{P}}\)\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\R}{\mathbb{R}}\)\(\newcommand{\N}{\mathbb{N}}\)\(\newcommand{\Z}{\mathbb{Z}}\)\(\newcommand{\bs}{\boldsymbol}\)

Основна теорія

Вступ

У моделі черги клієнти прибувають на станцію для обслуговування. Як завжди, терміни є загальними; ось кілька типових прикладів:

• Клієнтами є особи, а СТО - магазин.
• Клієнти - це запити файлів, а станція технічного обслуговування - веб-сервер.

Малюнок\(\PageIndex{1}\): Десять клієнтів і сервер

Моделі черги можуть бути досить складними, залежно від таких факторів, як розподіл ймовірностей, що регулює прибуття клієнтів, розподіл ймовірностей, який регулює обслуговування клієнтів, кількість серверів та поведінку клієнтів, коли всі сервери зайняті. Дійсно, теорія черг має свій власний лексикон для позначення деяких з цих факторів. У цьому розділі ми обговоримо кілька основних ланцюжків черг безперервного часу. У загальному сенсі основний інтерес до будь-якої моделі черги - це кількість клієнтів в системі як функція часу, і зокрема, чи можуть сервери адекватно обробляти потік клієнтів. Цей розділ паралельно секції на ланцюжках черг дискретного часу.

Наші основні припущення полягають у наступному:

1. Є\( k \in \N_+ \cup \{\infty\} \) сервери.
2. Клієнти прибувають відповідно до процесу Пуассона зі ставкою\( \mu \in (0, \infty) \).
3. Якщо всі сервери зайняті, новий клієнт переходить до кінця однієї лінії клієнтів, які очікують обслуговування.
4. Час, необхідний для обслуговування клієнта, має експоненціальний розподіл з параметром\( \nu \in (0, \infty) \).
5. Час обслуговування не залежить від клієнта до клієнта і не залежить від процесу прибуття.

Припущення (b) означає, що час між прибуттями клієнтів є незалежним і експоненціально розподіленим, з параметром\( \mu \). Припущення (c) означає, що у нас є модель першого, першого виходу, часто скорочено FIFO. Зверніть увагу, що в моделі є три параметри: кількість серверів\( k \), експоненціальний параметр,\( \mu \) який регулює прибуття, і експоненціальний параметр\( \nu \), який регулює час обслуговування. Особливі випадки\( k = 1 \) (єдиний сервер) і\( k = \infty \) (нескінченно багато серверів) заслуговують на окрему увагу. Як неважко здогадатися, припущення призводять до безперервного часу марковського ланцюга.

Нехай\( X_t \) позначають кількість клієнтів в системі (очікування в черзі або обслуговуються) за часом\( t \in [0, \infty) \). Потім\( \bs{X} = \{X_t: t \in [0, \infty)\} \) є безперервний час ланцюга Маркова на\( \N \), відомий як M/M/\( k \) ланцюг черги.

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

Для M/M/M/\( k \) ланцюга\( \bs{X} \),

1. Функція експоненціального параметра\( \lambda \) задається\( \lambda(x) = \mu + \nu x \) if\( x \in \N \) і if\( x \lt k \) і\( \lambda(x) = \mu + \nu k \) if\( x \in \N \) і\( x \ge k \).
2. Матриця переходу\( Q \) для ланцюга стрибків задається за допомогою\ begin {align*} Q (x, x - 1) & =\ frac {\ nu x} {\ mu +\ nu x},\; Q (x, x + 1) =\ frac {\ mu} {\ mu +\ nu x},\ n\ in\ N,\, x\ lt k\\ Q (x, x - 1) & =\ frac {\ nu k} {\ mu +\ nu k},\; Q (x, x + 1) =\ frac {\ mu} {\ mu +\ nu k},\ квад х\ в\ N, х\ ge k\ кінець {вирівнювати*}

Таким чином,\( k \) M/M/M/ланцюг - це ланцюг народження-смерть з 0 як відбиваюча гранична точка. Тобто, у стані\( x \in \N_+ \) наступний стан\( x - 1 \) або\( x + 1 \), перебуваючи в стані 0, наступний стан - 1. Коли\( k = 1 \) черга одного сервера, експоненціальний параметр у стані\( x \in \N_+ \) є\( \mu + \nu \) і ймовірності переходу для ланцюга стрибків є\[ Q(x, x - 1) = \frac{\nu}{\mu + \nu}, \; Q(x, x + 1) = \frac{\mu}{\mu + \nu} \] Коли\( k = \infty \), нескінченна черга сервера, випадки вище для\( x \ge k \) вакуумного, тому експоненціальний параметр у стані\( x \in \N \) є\( \mu + x \nu \) і ймовірності переходу\[ Q(x, x - 1) = \frac{\nu x}{\mu + \nu x}, \; Q(x, x + 1) = \frac{\mu}{\mu + \nu x} \]

Нескінченно малий генератор

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

Для\( k \)\( \bs{X} \) ланцюга черг M/M/ нескінченно малий генератор\( G \) задається за допомогою\ begin {align*} G (x, x) & = - (\ mu +\ nu x),\; G (x, x - 1) =\ nu x,\; G (x, x + 1) =\ mu;\ quad x\ in\ n,\, x\ lt k\\ G (x, x, x) = - (\ мю +\ ню к),\; Г (х, х - 1) =\ ню к,\; Г (х, х + 1) =\ му;\ квад х\ в\ N,\, x\ ge k\ end {align*}

Таким чином\( k = 1 \), одна черга сервера, генератор\( G \) дається,\( G(0, 0) = -\mu \),\( G(0, 1) = \mu \) в той час як для\( x \in \N_+ \),,\( G(x, x) = -(\mu + \nu) \),\( G(x, x - 1) = \nu \),\( G(x, x + 1) = \mu \). Для\( k = \infty \), нескінченного випадку сервера, генератор\( G \) задається\( G(x, x) = -(\mu + \nu x) \)\( G(x, x - 1) = \nu x \), і\( G(x, x + 1) = \mu \) для всіх\( x \in \N \).

Класифікація та обмежувальна поведінка

Знову ж таки, давайте\( \bs{X} = \{X_t: t \in [0, \infty)\} \) позначимо\( k \) ланцюг M/M/черги зі швидкістю прибуття\( \mu \), швидкістю обслуговування\( \nu \) і з\( k \in \N_+ \cup \{\infty\} \) серверами. Як зазначалося у вступі, принципове значення має питання про те, чи можуть сервери обробляти потік клієнтів, щоб черга з часом спорожнялася, або довжина черги зростає без обмежень. Щоб зрозуміти граничну поведінку, нам потрібно класифікувати ланцюг як перехідний, нульовий рекуррентний або позитивний рекуррент і знайти інваріантні функції. Це буде легко зробити, використовуючи наші результати для більш загальних ланцюгів безперервного часу народження-смерті. Зверніть увагу спочатку, що\( \bs{X} \) є нескоротним. Найкраще розглядати окремі серверні та нескінченні серверні випадки окремо.

Єдиний ланцюжок\( \bs{X} \) черги сервера

1. Тимчасовий якщо\( \nu \lt \mu \).
2. Нульовий повторюваний якщо\( \nu = \mu \).
3. Позитивні рецидивні якщо\( \nu \gt \mu \). Інваріантний розподіл - це геометричний розподіл по параметру\( \N \) with\( \mu / \nu \). Інваріантна функція щільності ймовірності\( f \) задається\[ f(x) = \left(1 - \frac{\mu}{\nu}\right) \left(\frac{\mu}{\nu}\right)^x, \quad x \in \N \]

Доказ

Це випливає безпосередньо з результатів для безперервного ланцюга народження-смерті, з постійною народжуваністю\( \N \) і постійною\( \nu \) смертністю\( \N_+ \).\( \mu \)

Результат має інтуїтивний сенс. Якщо швидкість обслуговування менше швидкості прибуття, ланцюг перехідний і довжина черги зростає до нескінченності. Якщо тариф обслуговування перевищує показник прибуття, ланцюг позитивний рецидивуючий. На кордоні між цими двома випадками, коли тарифи прибуття та обслуговування однакові, ланцюжок є нульовим повторюваним.

Нескінченний ланцюг черги сервера\( \bs{X} \) є позитивним повторюваним. Інваріантним розподілом є розподіл Пуассона з параметром\( \mu / \nu \). Інваріантна функція щільності ймовірності\( f \) задається\[ f(x) = e^{-\mu / \nu} \frac{\left(\mu / \nu\right)^x}{x!}, \quad x \in \N \]

Доказ

Це також випливає з результатів для безперервного ланцюга народження-смерті. У позначеннях цього розділу народжуваність\( \mu(x) = \mu \) постійна, бо\( x \in \N \) і смертність пропорційна кількості клієнтів в системі:\( \nu(x) = \nu x \) для\( x \in \N_+ \). Звідси інваріантна функція (унікальна аж до множення на константи)\[ x \mapsto \frac{\mu(0) \cdots \mu(x - 1)}{\nu(1) \cdots \nu(x)} = \frac{\mu^x}{\nu^x x!} \] нормалізована, це розподіл Пуассона з параметром\( \mu / \nu \).

Цей результат також має інтуїтивний сенс.