Задачи массового обслуживания

Тема 12 Задачи массового обслуживания.

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

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

Рис. 12.1 Схема СМО

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

Классификация СМО

СМО по наличию того или иного признака можно разделить следующим образом:

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

Рекомендуемые материалы

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

Для исследования СМО со случайным потоком необходимо, чтобы была задана или известна функция распределения вероятностей поступления требований в систему. Примером такой системы может служить хорошо налаженный монтаж какого-либо сооружения по чётко разработанному плану;

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

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

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

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

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

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

1) Если вновь поступившее требование на обслуживание застаёт все каналы обслуживания уже занятыми, и оно покидает систему, то имеем систему с отказом. Требование может покинуть систему и в том случае, когда очередь достигла определённых размеров. Если, например, на станции техобслуживания скопилось много автомашин, то целесообразнее покинуть систему; если при посадке самолета полоса приземления занята, он покидает аэродром;

2) Если поступившее требование застает все каналы обслуживания занятыми и становится в очередь, но находится в ней ограниченное время, после чего, не дождавшись обслуживания, покидает систему, то имеем систему с ограниченным ожиданием. Примером такого ''нетерпеливого требования'' может быть автосамосвал с раствором. Если время ожидания велико, то во избежание затвердения раствора он может быть разгружен на другой стройке;

3) Если поступившее требование, застав все каналы обслуживания занятыми, вынуждено ожидать своей очереди до тех пор, пока оно не будет обслужено, то имеем систему с ожиданием без ограничения. Пример: самолет, который находится на аэродроме до тех пор, пока не освободится взлётная полоса.

5. По способу выбора требования на обслуживание на системы с приоритетом, по мере поступления, случайно, последний обслуживается первым.

Иногда в этом случае говорят о дисциплине обслуживания.

1) Если СМО охватывает несколько категорий требований и по каким-либо соображениям необходимо соблюдать различный подход к их отбору, то имеем систему с приоритетом. Так, при поступлении изделий на стройплощадку в первую очередь монтируются те, которые необходимы в данный момент;

2) Если освободившийся канал обслуживает требование, ранее других поступившее в систему, то имеем СМО с обслуживанием требований по мере их поступления. Это наиболее распространенный класс систем. Например, покупатель, подошедший первым к продавцу, обслуживается первым. Этот способ выбора требований на обслуживание применяется там, где в силу технических, технологических и организационных условий требования не могут опережать друг друга;

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

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

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

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

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

9. По однородности требований, поступающих на обслуживание, на системы с однородными и неоднородными потоками требований. Так, если под погрузку прибывают автомобили одной грузоподъёмности, то такие требования называются однородными, если разной грузоподъёмности – то неоднородными.

10. По ограниченности потока требований на замкнутые и разомкнутые системы. Если поток требований ограничен, и требования, покинувшие систему, могут в неё возвращаться, то имеем замкнутую систему, в противном случае – разомкнутую. Примером замкнутой системы может служить система ЭВМ – пользователь, в которой пользователь, как правило, прикрепляется к ЭВМ и обслуживается ею в течение определённого времени.

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

В задачах анализа СМО в качестве основных показателей функционирования системы могут быть использованы:

- вероятность простоя канала обслуживания  ;

- вероятность того, что в системе находится  n  требований - ;

- среднее число требований, находящихся в системе (сфере обслуживания)  ;

- среднее число требований, находящихся в очереди, , где  - число каналов обслуживания;

- среднее время ожидания требований в очереди  :

для разомкнутой системы   где  - интенсивность поступления потока требований в систему;

для замкнутой системы   где  m – число требований, нуждающихся в обслуживании;

- среднее время ожидания требований в системе  ;

- среднее число свободных каналов обслуживания 

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

- среднее число заявок, находящихся на обслуживании в период  

-  формула Литтла, где  - средняя интенсивность поступления требований,  - средняя продолжительность обслуживания одной заявки.

Задачи анализа одноканальных систем массового обслуживания

          Как видно из приведённой классификации СМО, имеется большое число разновидностей СМО. Ограничимся наиболее часто встречающимися СМО:

- детерминированной одноканальной;

- одноканальной разомкнутой с ожиданием с простейшим потоком поступления требований в систему;

- одноканальной замкнутой (поток требований пуассоновский) с ожиданием.

(Пуассоново распределение – распределение случайной величены, при котором она может принимать дискретные значения из счётного множества 0, 1, 2, … с вероятностью

параметр распределения).

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

Задача анализа детерминированной системы

Постановка задачи

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

Выявление основных особенностей, взаимосвязей и количественных закономерностей

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

Рис. 12.2 Схема работы системы

Пока обслуживается очередь из  n  требований в течение времени , вновь поступит на обслуживание    требований:

.

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

.

Это происходит до тех пор, пока ,  после чего очередь исчезнет.

Весь процесс функционирования СМО представим в аналитическом виде.

Построение математической модели

Если Вам понравилась эта лекция, то понравится и эта - 20 Структура общества и брачно-семейные отношения.

Время, через которое очередь исчезнет, можно представить в таком виде:

Исследование математической модели.

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

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