ГЛАВА VIII. ПРИМЕНЕНИЕ МЕТОДА СТАТИСТИЧЕСКИХ ИСПЫТАНИЙ ДЛЯ РЕШЕНИЯ ЗАДАЧ, СВЯЗАННЫХ С МАССОВЫМ ОБСЛУЖИВАНИЕМ

§ 27. Вводные замечания

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

Для обслуживания заявок в системе (агрегате) имеются линии (каналы), выполняющие совокупность операций, подразумеваемых под словом «обслуживание». Так, для автозаправочной станции заявками являются автомобили, прибывающие в случайные моменты времени для пополнения запаса горючего, а линиями — бензоколонки, производящие заправку автомобилей.

Будем считать в общем случае, что обслуживающий агрегат состоит из линий, способных одновременно и независимо друг от друга обслуживать заявки. В любой момент времени линия может находиться в одном из двух состояний: линия свободна, линия занята. Каждая заявка, поступающая в агрегат, либо принимается к обслуживанию (если имеется свободная линия), либо остается в системе в течение некоторого времени — времени пребывания в агрегате (если все линии заняты).

В течение времени заявка должна быть принята к обслуживанию, в противном случае она считается потерянной (получает отказ),

В зависимости от величины обслуживающие системы обычно разделяют на три класса: системы с отказами системы с ожиданием смешанные системы

Кроме для характеристики свойств обслуживающего агрегата используется также — время занятости линии.

Как правило, параметры являются случайными величинами с заданными законами (или совместным законом) распределения. В частном случае один из них или оба могут оказаться фиксированными.

Заявка, принятая к обслуживанию, занимает одну из линий на время По истечении этого времени линия освобождается и оказывается способной приступить к обслуживанию новой заявки.

Рассмотрение процесса обслуживания отдельно взятой заявки представляет лишь ограниченный интерес. Обычно предполагается, что заявки образуют поток — последовательность заявок со специальным чередованием моментов их появления во времени. Если, с точки зрения обслуживания, все заявки данного потока оказываются равноправными, то играет роль лишь сам факт наступления или ненаступления в данный момент времени события, состоящего в появлении заявки. Такого рода потоки называются потоками однородных событий.

Способы математического описания потоков заявок и процессов обслуживания, которые мы рассмотрим ниже, дают возможность ставить задачи об оценке качества обслуживания, о выборе оптимальных значений параметров обслуживающих систем, о структуре этих систем и т. д. Эти вопросы имеют важное прикладное значение.

Это послужило причиной интенсивной разработки аналитического аппарата теории массового обслуживания, существенным образом использующего вероятностные методы. Однако основные результаты, рассматриваемые в литературе по этому вопросу (см. [11], [35] и др.), посвящены главным образом изучению наиболее простых случаев. Это относится как к строению входного потока заявок, поступающих на обслуживание, так и

к структуре процессов функционирования систем массового обслуживания. Поэтому имеющийся в настоящее время аналитический аппарат может лишь частично удовлетворять возрастающим запросам практики.

При сложившейся ситуации, очевидно, целесообразно для решения актуальных прикладных задач, не поддающихся обработке при помощи существующих аналитических методов, использовать метод статистических испытаний.

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

В настоящей главе рассматриваются две группы вопросов. К первой группе относится методика решения задач, связанных с массовым обслуживанием, при условии, что поток заявок представляет собой поток однородных событий. Вторая группа посвящена рассмотрению значительно более сложных задач. Основная особенность этих задач заключается в рассмотрении потоков заявок с учетом существенной неоднородности событий потока. Последнее обстоятельство приводит, как правило, к необходимости считаться с тем, что значения параметров обслуживающей системы в общем случае не остаются постоянными в процессе обслуживания, а определяются совокупностью характеристик потока.

Обратимся сначала к первой группе вопросов.

Для того чтобы описать поток однородных событий, достаточно задать закон распределения моментов времени, в которые данные события наступают.

Для удобства дальнейших рассмотрений, как это принято в теории массового обслуживания (см., например, [11]), целесообразно от величин перейти к случайным величинам таким, что

Случайные величины являются длинами интервалов времени между последовательными моментами

Совокупность случайных величин считается заданной, если определена совместная функция распределения

Обычно рассматривают только непрерывные случайные величины поэтому часто пользуются соответствующей (8.2) функцией плотности

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

Одним из такого рода классов потоков однородных событий является класс потоков с ограниченным последействием, для которых случайные величины независимы. Поэтому

Функции при представляют собой условные функции плотности при условии, что в начальный момент интервала поступила заявка. В отличие от этого функция является безусловной функцией плотности, так как относительно появления или непоявления заявки в начальный момент времени не делается никаких предположений.

Широкое практическое применение имеют так называемые стационарные потоки, для которых вероятный режим их во времени не изменяется. Точная формулировка этого свойства состоит в том, что вероятность появления заявок за промежуток времени не зависит от а зависит только от и Для стационарных потоков с ограниченным последействием имеют место соотношения

где X — плотность стационарного потока — среднее количество заявок, поступающих в единицу времени.

Потоки с ограниченным последействием (особенно стационарные) представляют собой весьма удобные схемы, которые можно использовать для аппроксимации различных потоков, встречающихся при решении прикладных задач.

В качестве примера рассмотрим так называемый простейший поток — ординарный стационарный поток без последействия.

Функция плотности для такого потока имеет вид

где X — плотность потока.

Заметим, что в случае простейшего потока функция плотности совпадает с (8.5).

Закон распределения числа заявок в интервале времени длины является законом Пуассона

Простейший поток и его использование широко освещаются в литературе по теории массового обслуживания (см. [11], [35] и др.). Другие примеры потоков с ограниченным последействием будут рассмотрены ниже.

Реальный процесс функционирования системы массового обслуживания для удобства исследования удобно представлять в виде последовательности отдельных актов (фаз) обслуживания, выполняемых различными агрегатами. При этом, как правило, соблюдается такой порядок, при котором следующий агрегат может приступить к обслуживанию заявки лишь тогда, когда работа предыдущего агрегата с данной заявкой полностью закончена.

В частном случае обслуживание может быть однофазным.

Простейшим примером многофазного обслуживания может служить обслуживание покупателей в магазине. Сначала покупатель занимает одного из работников прилавка, демонстрирующего товары и оформляющего товарные чеки (первая фаза). Отобрав товары и получив чек, покупатель должен пройти через вторую фазу — оплатить чек в кассе. И только с оплаченным чеком

покупатель может быть принят на обслуживание в отдел контроля и выдачи покупок (третья фаза).

Более сложным примером многофазного обслуживания может быть технологический процесс, связанныи с последовательной обработкой изделий при помощи, оборудования различного назначения. Изделие может поступить на обработку станком 1-й фазы лишь тогда, когда его обработка на станке фазы закончена.

Краткая характеристика процесса обслуживания на одной из фаз была рассмотрена выше. Сейчас обратим внимание на возможные варианты порядка занятия линий и принятия заявок на обслуживание.

Поступившая в систему заявка может занимать только свободные линии. Относительно порядка занятия линий могут быть сделаны различные предположения. Наиболее широко на практике используются следующие три предположения:

а) Линии занимаются в порядке их номеров. Линия с большим номером не может быть привлечена к обслуживанию заявки, если имеется свободная линия с меньшим номером.

б) Линии занимаются в порядке очереди. Освободившаяся линия поступает в очередь и не начинает обслу-, живания заявок до израсходования всех ранее освободившихся линий.

в) Линии занимаются в случайном, порядке в соответствии с заданными вероятностями. Если в момент поступления очередной заявки имеется свободных линий, то в простейшем случае вероятность занять некоторую определенную линию может быть принята равной . В более сложных случаях вероятности считаются зависящими от номеров линий, моментов их освобождения и других параметров.

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

а) Заявки принимаются к обслуживанию в порядке очереди. Освободившаяся линия приступает к

обслуживанию той заявки, которая ранее других поступила в систему.

б) Заявки принимаются к обслуживанию по минимальному времени получения отказа. Освободившаяся линия приступает к обслуживанию той заявки, которая в кратчайшее время может получить отказ.

в) Заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии имеется заявок в очереди, то в простейшем случае вероятность выбрать для обслуживания некоторую определенную заявку может быть принята равной . В более сложных случаях вероятности считаются зависящими от времени пребывания заявки в системе, времени, остающегося до получения отказа, и других параметров.

Перечисленными предположениями, естественно, охватываются не все случаи, возникающие на практике, а лишь наиболее распространенные.

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

Будем также предполагать, что линия, вышедшая из строя по причине неполной надежности, может быть введена в строй (отремонтирована), для чего требуется затратить время Величину будем считать случайной величиной с заданным законом распределения.

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

Рассмотрев основные модификации процесса функционирования систем массового обслуживания, перейдем

к вопросу о величинах, которые являются искомыми при решении задач, связанных с массовым обслуживанием (показатели качества обслуживания).

Для систем с отказами наиболее широко используемым показателем качества обслуживания является средняя доля отказов за промежуток времени Эта величина определяется следующим образом.

Рассмотрим совокупность реализаций процесса обслуживания на интервале Количество заявок, поступивших на обслуживание за этот интервал времени для выбранной наудачу реализации, будет случайной величиной Пусть является средним значением величины т. е. средним количеством заявок, поступающих на обслуживание в течение интервала времени Количество заявок получивших отказ в течение того же интервала времени, также будет случайной величиной. Среднее значение является средним количеством отказов за интервал времени Тогда средняя доля отказов определяется как

Кроме средней доли отказов как показатель качества обслуживания иногда используется вероятность не получить ни одного отказа (обслужить все заявки) в течение интервала времени или другие параметры закона распределения количества отказов

В случае стационарного входа потока величина не зависит от и может быть выражена соотношением

где — плотность потока заявок.

Для систем обслуживания с постоянными параметрами и моментов времени, достаточно удаленных от начала обслуживания, величина также не зависит

от и может быть выражена соотношением, аналогичным (8. 8),

где — плотность потока отказов.

Тогда средняя доля отказов будет постоянной величиной

не зависящей от длительности интервала времени . В связи с соотношением (8.10) величина имеет также смысл вероятности отказа для заявки, поступившей в систему в произвольный момент времени.

В случае систем с ожиданием показателями качества обслуживания могут быть среднее значение времени ожидания или среднее значение длины очереди (количество заявок, ожидающих обслуживания). Иногда используются и другие параметры закона распределения времени ожидания или длины очереди.

Для смешанных систем показателями качества обслуживания служат как те, так и другие величины.

Известные (см. [11], [14], [15] и др.) аналитические соотношения теорий массового обслуживания, связывающие характеристики потока заявок и параметры системы с показателями качества обслуживания, обычно представляют собой асимптотические формулы, дающие значения показателей для моментов времени, достаточно удаленных от начала обслуживания. Такие формулы имеются главным образом для случая, когда заявки образуют простейший (пуассоновский) поток однородных событий, а обслуживание является однофазным.

В качестве примера такого рода асимптотических формул можно привести формулу Эрланга (см., например, [11]).

Рассмотрим однофазную систему с отказами состоящую из линий. Для обслуживания поступившей заявки линии выбираются в случайном порядке с одинаковыми вероятностями. Время занятости линии (время обслуживания) является случайной величиной с конечным математическим ожиданием

Предположим, что в такую систему поступает простейший поток заявок с плотностью .

Тогда асимптотическое (при ) значение вероятности отказа может быть определено по формуле

Рассмотренная схема обслуживания является одной из наиболее элементарных. Для других схем имеющиеся формулы оказываются более сложными. Мы не будем останавливаться на других формулах такого типа, они рассматриваются в упоминавшейся выше литературе по теории массового обслуживания.

Для многих прикладных задач предположения, при которых справедливы такие формулы, оказываются слишком стеснительными. При решении задач методом статистических испытаний некоторые предположения могут быть существенно ослаблены.

В первую очередь это относится к многофазному об: служиванию. Мы будем рассматривать обслуживающие системы, состоящие из нескольких последовательно действующих в общем случае неоднотипных агрегатов.

Другим важным обобщением задачи является предположение о характере потока заявок, поступающих на обслуживание. Допускается рассмотрение потоков однородных событий с практически произвольным законом распределения. Последнее обстоятельство оказывается существенным по следующим двум причинам. Во-первых; реальные потоки заявок в некоторых случаях заметно отличаются от простейшего. Для пояснения второй причины предположим, что исходный поток заявок достаточно точно аппроксимируется простейшим потоком. При этом поток заявок, обслуженных на первой фазе, уже, строго говоря, не будет простейшим. Поскольку поток, являющийся выходным для первой фазы, будет входным потоком для агрегата, обслуживающего заявки на второй фазе, мы снова приходим к задаче обслуживания потоков, не являющихся простейшими,

В качестве следующих обобщений задачи будем рассматривать схемы обслуживания с произвольными предположениями относительно порядка привлечения линий и выбора заявок, а также судьбы заявок, обслуживаемых линиями, выходящими из строя по причине неполной надежности.

Кроме того, ряд существенных обобщений постановки задачи будет рассмотрен во второй части настоящей главы.

Сущность метода статистических испытаний применительно к задачам массового обслуживания состоит в следующем. Строятся алгоритмы, при помощи которых можно вырабатывать случайные реализации заданных потоков однородных событий, а также «моделировать» процессы функционирования обслуживающих систем. Эти алгоритмы используются для многократного воспроизведения реализаций случайного процесса обслуживания при фиксированных условиях задачи. Получаемая при этом информация о состояниях процесса подвергается статистической обработке с целью оценки величин, являющихся показателями качества обслуживания.

Метод статистических испытаний позволяет более полно, по сравнению с асимптотическими формулами, исследовать зависимость качества обслуживания от характеристик потока заявок и параметров обслуживающей системы.

Это достигается благодаря двум обстоятельствам. Во-первых, при решении задач теории массового обслуживания методом статистических испытаний может быть использована более обширная информация о процессе, чем это обычно удается сделать, применяя аналитические методы. Например, в рамках условий, при которых справедлива формула Эрланга, из соотношения (8.11) мы можем получить лишь значение величины — вероятности отказа или средней доли отказов. Метод статистических испытаний в этом случае позволил бы получить оценку не только для средней доли отказов, но и для любого параметра закона распределения доли отказов.

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

удаленным от начала процесса. Реально, для моментов времени, близких к началу процесса, когда еще не наступил стационарный режим, значения показателей качества обслуживания в общем случае существенно отличаются от асимптотических значений. Метод статистических испытаний позволяет достаточно обстоятельно изучать переходные режимы.

Перейдем к краткому изложению методики моделирования процессов массового обслуживания на электронных цифровых машинах универсального назначения. В первую очередь рассмотрим способы формирования реализаций случайных потоков однородных событий, используемых при моделировании процессов обслуживания.