Что будет происходить с вероятностями состояний при t ( ( ? Будут ли p1(t), p2(t),... стремиться к каким-то пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют.
Финальную вероятность состояния Si можно истолковать как среднее относительное время пребывания системы в этом состоянии.
Граф состояний для схемы гибели и размножения имеет вид, показанный на
рис. 1. Особенность этого графа в том, что все состояния системы можно
вытянуть в цепочку, в которой каждое из средних состояний связано прямой и
обратной стрелкой с каждым из соседних состояний — правым и левым, а
крайние состояния — только с одним соседним состоянием. Термин «схема
гибели и размножения» ведет начало от биологических задач, где подобной
схемой описывается изменение численности популяции.
Схема гибели и размножения
(01 (12 (23 (k-
1,k (k,k+1 (n-1,n
| | | | | | | | | | | | | | | |
|S0 | |S1 | |S2 | |...| |Sk | |...| |Sn-1 | |Sn |
| | | | | | | | | | | | | | | |
| | | | | | |...| | | |...| | | | |
| | | | | | | | | | | | | | | |
| | | | | | |ю | | | | | | | | |
(10 (21 (32 (k,k-
1 (k+1,k (n,n-1
[pic][pic][pic] [pic]
( — интенсивность потока; p0, pk — финальные вероятности состояний
Формулы Литтла
[pic] Lсист — среднее число заявок в системе;
Wсист — среднее время пребывания заявки в системе;
Wоч[pic]L оч Lоч — среднее число заявок в очереди;
Wоч — среднее время пребывания заявки в очереди
( — интенсивность потока обслуживаний; ( — интенсивность потока заявок
( /( = ( (приведенная интенсивность потока заявок)
( — среднее число заявок, приходящее за среднее время обслуживания одной
заявки рис. 1
2.2 Классификация систем массового обслуживания
При исследовании операций часто приходится сталкиваться с работой систем массового обслуживания. СМО могут быть одноканальными и многоканальными.
Процесс работы СМО представляет собой случайный процесс с дискретными состояниями и непрерывным временем; состояние СМО меняется скачком в моменты появления каких-то событий (прихода новой заявки, окончания обслуживания, момента, когда заявка, которой «надоело ждать», покидает очередь).
Предмет теории массового обслуживания — построение математических моделей, связывающих заданные условия работы СМО (число каналов, их производительность, правила работы, характер потока заявок) с интересующими нас характеристиками — показателями эффективности СМО, описывающими, с той или другой точки зрения, ее способность справляться с потоком заявок. В качестве таких показателей (в зависимости от обстановки и целей исследования) могут применяться разные величины, например: среднее число заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов; среднее число заявок в очереди и среднее время ожидания обслуживания; вероятность того, что число заявок в очереди превысит какое-то значение, простои, и т. д.
Математический анализ работы СМО очень упрощается, если процесс этой работы — марковский. Для этого достаточно, чтобы все потоки событий, переводящие систему из состояния в состояние (потоки заявок, «потоки обслуживания»), были простейшими. Если это свойство нарушается, то математическое описание процесса становится гораздо сложнее и довести его до явных, аналитических формул удается лишь в редких случаях. Однако аппарат простейшей, марковской теории массового обслуживания может пригодиться для приближенного описания работы СМО даже в тех ситуациях, когда потоки событий — не простейшие. Во многих случаях для принятия разумного решения по организации работы СМО вовсе и не требуется точного знания всех ее характеристик — зачастую достаточно и приближенного, ориентировочного.
Системы массового обслуживания делятся на типы (или классы) по ряду
признаков. Первое деление: СМО с отказами и СМО с очередью. В СМО с
отказами заявка, поступившая в момент, когда все каналы заняты, получает
отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует.
Примеры СМО с отказами встречаются в телефонии: заявка на разговор,
пришедшая в момент, когда все каналы связи заняты, получает отказ и
покидает СМО необслуженной. В СМО с очередью заявка, пришедшая в момент,
когда все каналы заняты, не уходит, а становится в очередь и ожидает
возможности быть обслуженной. На практике чаще встречаются (и имеют большее
значение) СМО с очередью; недаром теория массового обслуживания имеет
второе название: «теория очередей».
СМО с очередью подразделяются на разные виды, в зависимости от того, как организована очередь — ограничена она или не ограничена. Ограничения могут касаться как длины очереди, так и времени ожидания (так называемые
«СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и
«дисциплина обслуживания» — заявки могут обслуживаться либо в порядке поступления (раньше пришла, раньше обслуживается), либо в случайном порядке. Нередко встречается так называемое обслуживание с приоритетом — некоторые заявки обслуживаются вне очереди. Приоритет может быть как абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под обслуживания заявку с низшим, так и относительным — когда начатое обслуживание доводится до конца, а заявка с более высоким приоритетом имеет лишь право на лучшее место в очереди.
Существуют СМО с так называемым многофазовым обслуживанием, состоящим из нескольких последовательных этапов или «фаз» (например, покупатель, пришедший в магазин, должен сначала выбрать товар, затем оплатить его в кассе, после чего получить на контроле).
Кроме этих признаков, СМО делятся на два класса: «открытые» и
«замкнутые». В открытой СМО характеристики потока заявок не зависят от
того, в каком состоянии находится сама СМО (сколько каналов занято). В
замкнутой СМО — зависят. Например, если один рабочий обслуживает группу
станков, время от времени требующих наладки, то интенсивность потока
«требований» со стороны станков зависит от того, сколько их уже неисправно
и ждет наладки. Это — пример замкнутой СМО.
Рассмотрим вывод упомянутой ранее формулы Литтла, связывающей (для предельного, стационарного режима) среднее число заявок Lсист, находящихся в системе массового обслуживания (т. е. обслуживаемых или стоящих в очереди), и среднее время пребывания заявки в системе Wсист.
Рассмотрим любую СМО (одноканальную, многоканальную, марковскую, немарковскую, с неограниченной или с ограниченной очередью) и связанные с нею два потока событий: поток заявок, прибывающих в СМО, и поток заявок, покидающих СМО. Если в системе установился предельный, стационарный режим, то среднее число заявок, прибывающих в СМО за единицу времени, равно среднему числу заявок, покидающих ее, так как оба потока имеют одну в ту же интенсивность (.
Обозначим: X(t)—число заявок, прибывших в СМО до момента t, Y(t) —
число заявок, покинувших СМО до момента t. И та, и другая функции являются
случайными и меняются скачком (увеличиваются на единицу) в моменты приходов
заявок (X(t)) и уходов заявок (Y(t)). Для любого момента t их разность Z(t)
= X(t) - Y(t) — это число заявок, находящихся в СМО.
Рассмотрим очень большой промежуток времени T и вычислим для него среднее число заявок, находящихся в СМО. Оно будет равно интегралу от функции Z(t) на этом промежутке, деленному на длину интервала T:
[pic] (7)
Данный интеграл представляет собой площадь фигуры, заключенной между
X(t) и Y(t). Фигура состоит из прямоугольников, каждый из которых имеет
высоту, равную единице, и основание, равное времени пребывания в системе
соответствующей заявки (первой, второй и т. д.). Обозначим эти времена как
t1, t2,... Правда, под конец промежутка Т некоторые прямоугольники войдут в
эту фигуру не полностью, а частично, но при достаточно большом Т этим можно
пренебречь. Таким образом, можно считать, что
[pic], (8)
где сумма распространяется на все заявки, пришедшие за время Т.
Разделим правую и левую часть (8) на длину интервала Т. Получим, с учетом (7):
[pic] (9)
Разделим и умножим правую часть (9) на интенсивность (:
[pic] (10)
Величина T( — это среднее число заявок, пришедших за время Т. Если мы разделим сумму всех времен ti на среднее число заявок, то получим среднее время пребывания заявки в системе Wсист- Итак,
[pic] (11)
Это и есть формула Литтла: для любой СМО, при любом характере потока заявок, при любом распределении времени обслуживания, при любой дисциплине обслуживания среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.
Точно таким же образом выводится вторая формула Литтла, связывающая среднее время пребывания заявки в очереди Wоч и среднее число заявок в очереди Lоч.
Lоч = ( Wоч
2.3 Варианты систем массового обслуживания
1. n-канальная СМО с отказами
A — абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени);
Q — относительная пропускная способность (средняя доля пришедших заявок, обслуживаемых системой);
Pотк — вероятность того, что заявка покинет СМО необслуженной;
[pic] — среднее число занятых каналов; [pic];
[pic]; [pic];
[pic] ; [pic];
[pic]; [pic]
2. Одноканальная СМО с неограниченной очередью
Pзан — вероятность того, что канал занят; Lоб — среднее число заявок под обслуживанием
[pic]; [pic];
[pic];
[pic];
[pic]; [pic] ;
[pic] ; [pic]Lоч[pic] ;
Wоч[pic]
3. Одноканальная СМО с неограниченной очередью, простейшим потоком заявок и произвольным распределением времени обслуживания
На одноканальную СМО поступает простейший поток заявок с интенсивностью
(. Время обслуживания имеет произвольное распределение с математическим
ожиданием [pic] и коэффициентом вариации ((. (( — отношение среднего
квадратического отклонения времени обслуживания к его математическому
ожиданию.
Формулы Полячека — Хинчина:
Lоч[pic] ; Lсист[pic]
Далее, согласно формуле Литтла:
Wоч[pic] ; Wсист[pic]
4. Одноканальная СМО с произвольным потоком заявок и произвольным распределением времени обслуживания
Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный поток заявок с интенсивностью ( и коэффициентом вариации ((, 0 < (( < 1. Время обслуживания также имеет произвольное распределение со средним значением [pic] и коэффициентом вариации ((, 0 (( < 1. Для этого случая точных аналитических формул получить не удается; можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу.
[pic]Lоч[pic]
[pic][pic]
Если входящий поток — простейший, то обе оценки — верхняя и нижняя — совпадают, и получается формула Полячека — Хинчина. Для грубо приближенной оценки средней длины очереди М. А. Файнбергом получена формула:
Lоч [pic][pic] Lсист = Lоч + (
Средние времена пребывания заявки в очереди и в системе вычисляются через Lоч и Lсист по формуле Литтла делением на (
2.4 Математическое описание разрабатываемой модели.
На вход системы из N станций поступает поток заявок с заданными
(экспоненциальным или нормальным) законом распределения времени прихода,
интенсивностью входного потока ( и, при нормальном распределении,
коэффициентом вариации ((. Каждая станция рассматривается, как
одноканальная СМО с неограниченной очередью. На каждой станции задано
среднее время обслуживания [pic] и, при нормальном распределении,
коэффициент вариации ((. На выходе станций поток заявок может ветвиться,
также может происходить отбраковка заявок. Это изменяет интенсивность
входного потока на последующих станциях.
При имитационном моделировании поэтапно имитируется (с использованием генератора случайных чисел) весь описанный процесс: моделируются входной поток и потоки обслуживаний, имитируются процессы ветвления и объединения потоков, а также процесс отбраковки заявок.
Расчетно-формульная модель такой системы может рассматриваться только в случае, когда существуют финальные вероятности. Для таких СМО финальные вероятности существуют только тогда, когда станции не перегружены, т. е для всех станций выполняется условие ([pic])
Глава 3
Создание программы
3.1 Структура программы
Выделим основные составные части проекта: Form1 («Задание связей между
рабочими станциями») — форма для создания связей между станциями, FormTabl
(«Создание матрицы связей») — форма для задания коэффициентов связей,
FormMultiMass («Модель многофазной многопоточной системы обслуживания») —
форма для ввода входных параметров, FormRes («Результаты моделирования
многофазной системы обслуживания») — форма для вывода результатов
моделирования, ModStation1 — основной вычислительный модуль.
На Form1 помещены следующие компоненты: Frame — для разделения формы на несколько областей, Line и Shape — для графического отображения связей между станциями, CommandButton — для обозначения станций, реализации процедуры задания связей между станциями и перехода к другим формам.
На FormTabl помещены компоненты: Label — для обозначения названий строк и столбцов матрицы связей, TextBox — для обозначения матрицы связей и ввода коэффициентов, CommandButton — для запуска проверки правильности задания коэффициентов связей и перехода к другим формам.
На FormMultiMass помещены компоненты: Frame — для разделения формы на несколько областей, TextBox — для ввода параметров, Label — для обозначения названия вводимого параметра, OptionButton — для организации выбора типа распределения, ProgressBar — для обозначения прохождения процесса моделирования, CommandButton — для начала ввода параметров, запуска процесса моделирования, перехода к другим формам и выхода из программы.
На FormRes помещены компоненты: SSTab — для разделения формы на две
страницы (графиков и числовых результатов), Frame — для разделения страницы
числовых результатов на несколько областей, Label — обозначения названия
выводимого показателя, PictureBox — для вывода графических результатов
моделирования, TextBox — для вывода числовых результатов моделирования,
CommandButton — для возвращения к формам, используемым для ввода входных
параметров.
3.2 Алгоритм работы программы
Рассмотрим обобщенный алгоритм работы программы, представленный укрупненными блоками, затем более детально рассмотрим реализацию каждого из блоков и приведем описание используемых переменных и функций.
Обобщенный алгоритм работы программы показан на рис. 2:
Начало
Ввод исходных данных
Н Ввод Д корректен?
Создание массива переходов Н
Расчет по
формулам?
Переход к первой станции
Д
Создание входного массива на текущей станции
Расчет по имита- Расчет по
ционной модели формулам
Нужна Д сортировка?
Сортировка
Вывод рассчитанных
Н показателей
Создание выходного массива на текущей станции
Н Продолжать
работу?
Н Последняя
Конец станция?
Переход к
Д следующей Д станции рис. 2
Программу можно поделить на две части: имитационная модель системы и
расчетно-формульная модель. Для начала функционирования любой модели
необходимо задать ряд входных параметров. Пользователь должен выбрать тип
распределения времени прихода заявок на первую станцию (экспоненциальное —
DistIndex = 0 или нормальное — DistIndex = 1) и тип распределения времени
обслуживания заявок по станциям (экспоненциальное — DistIndex1 = 0 или
нормальное — DistIndex1 = 1). Выбор осуществляется с помощью связанных пар
компонентов OptionButton. Также пользователь задает количество рабочих
станций — m (m = 1 — 10), число заявок на входе — n, среднее время между
заявками во входном потоке — Ta и, при нормальном распределении на входе,
стандартное отклонение (в % от среднего) — DTa (перечисленные параметры
вводятся с помощью компонентов TextBox). Затем, при помощи компонентов
CommandButton на форме «Задание связей между рабочими станциями», задаются
связи между станциями, каждая из которых обозначаются линией, соединяющей
две станции с кружком на том конце, куда связь приходит, далее, с помощью
матрицы связей на форме «Создание матрицы связей», задаются весовые
коэффициенты связей — pi(i). Матрица составлена из компонентов TextBox.
Далее, для каждой станции, также при помощи компонентов TextBox, задается
среднее время обслуживания — Ts(k), вероятность снятия заявки на выходе i-
ой станции — Pr(k) и, при нормальном распределении времени обслуживания,
стандартное отклонение (в % от среднего) — DTs(k).
После ввода весовых коэффициентов связей предусмотрена процедура
проверки на корректность ввода. В случае некорректного задания
коэффициентов, пользователю выдается сообщение об этом — MsgBox, и строка
матрицы связей, в которой были заданы некорректные значения, очистится.
Корректность проверяется через суммарные коэффициенты перехода: суммарный
коэффициент перехода в конце каждой строки должен равняться единице. Так
как коэффициенты определены типом Single, то для избежания ошибок, которые
могут возникнуть в результате погрешности вычислений, производимых с
переменными этого типа, проверка на равенство 1 заменяется проверкой на
принадлежность интервалу (0.9999; 1.0001).
Далее, рассмотрим отдельно структуру каждой части.
3.3 Расчетно-формульная модель.
При расчете показателей по формулам, после задания пользователем всех
необходимых входных параметров, производится расчет выходных параметров.
Вначале рассчитываются доля заявок (от исходного количества заявок,
пришедшего на первую станцию), пришедшая на последующие станции — kz(k) и
среднее время между заявками на входе каждой станции (величина, обратная
интенсивности входного потока) — kf(k).
Далее, происходит расчет показателей по формулам, соответствующим типам распределения входного потока и потоков обслуживания, и вывод результатов расчета (см. главу 2).
3.4 Имитационная модель
При расчете показателей с помощью имитационного моделирования вначале
создается двумерный массив переходов — a1(i, k), где k — номер станции, а i
— номер заявки. При создании данного массива с использованием случайных
чисел, имитируются процесс прохождения заявок по станциям (на основании
заданных коэффициентов переходов) и процесс отбраковки заявок (на основании
заданных вероятностей снятия заявок на выходе станций). Если заявка пришла
на станцию, то массиву в этой позиции присваивается значение 1; если же
заявка не пришла на станцию, то массиву в данной позиции присваивается
нулевое значение. Одновременно с созданием массива переходов производится
расчет количества снятых заявок по станциям — NumRef(k).
Далее, для каждой станции формируется входной массив (времен прихода
заявок на станцию) — a2(i, k) и выходной массив (времен выхода заявок со
станции) — a3(i, k), где k — номер станции, а i — номер заявки. Входной
массив первой станции образуется с использованием вспомогательной функции
Rexp(T As Single) — для экспоненциального распределения (или функции
Rnorm(MT As Single, DT As Single) — для нормального распределения).
Выходной массив первой станции образуется из входного массива, с
использованием тех же функций и функции Gener(nst As Integer). Входные
массивы последующих станций образуются в соответствии с массивом переходов
из выходных массивов предыдущих станций. В случае, когда заявки попадают на
вход данной станции с нескольких станций (sort > 1), производится
сортировка времен прихода заявок по возрастанию, с использованием
вспомогательной функции Sort1(nst As Integer). После создания входного
массива, на каждой последующей станции, создается выходной массив, с
использованием входного массива и вспомогательных функций: Gener(nst As
Integer), Rexp(T As Single) и Rnorm(MT As Single, DT As Single).
