:: Pascal Page :: Системы массового обслуживания (СМО)

Системы массового обслуживания (СМО)

Классификация СМО	Практический пример моделирования СМО
Показатели эффективности СМО
Экономические показатели СМО

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

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

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

Системы массового обслуживания классифицируют по разным признакам. К таким признакам относятся условия ожидания требования начала обслуживания. В соответствии с этим признаком системы подразделяются на следующие виды:

Системы массового обслуживания с потерями (отказами):

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

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

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

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

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

По месту нахождения источника требований системы массового обслуживания делятся на:

разомкнутые, когда источник находится вне системы;
замкнутые, когда источник находится в самой системе.

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

Показатели эффективности СМО

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

Показатели эффективности обычно формируются на основе полученных из расчетов значений вероятностей состояний системы:

Вероятность того, что поступающее в систему требование откажется присоединяться к очереди и теряется, (Р_отк).

Этот показатель для системы массового обслуживания с отказами равен вероятности того, что в системе находится столько требований, сколько она содержит приборов (каналов) обслуживания:
```
P_отк = P_m
```
, где m - число каналов обслуживания.

Для системы с ограниченной длиной очереди Р_отк равно вероятности того, что в системе находится m+L требований:
```
P_отк = P_{m + L}
```
, где L — допустимая длина очереди.

Противоположным показателем является вероятность обслуживания требования:
```
P_обсл = 1 - P_отк
```
Среднее количество требований, ожидающих начала обслуживания:
```
     m+L
M_ож = ∑[(n-m)*P_n]
    n=m+1
```
где P_n — вероятность того, что в системе находятся n требований.

При условии простейшего потока требований и экспоненциального закона распределения времени обслуживания формулы для М_ож принимают следующий вид:
- система с ограниченной длиной очереди:
```
                     L
M_ож = (P₀*ρ^m / m!) * ∑(n*(ρ/m)ⁿ)
                    n=1
```
  , где
    ρ = λ/μ,
    λ - интенсивность входящего потока требований (среднее число требований, поступающих в единицу времени),
    μ - интенсивность обслуживания (среднее число обслуженных требований в единицу времени)
- система с ожиданием:
```
M_ож = ((P₀*ρ^m+1) / (m * m!)) * (1 / (1 - ρ/m)²)
```
Относительная (q) и абсолютная (А) пропускные способности системы. Эти величины находят соответственно по формулам:
```
q = 1 - P_отк
A = λ*q
```
Среднее число занятых обслуживанием приборов в случае экспоненциального характера потока требований и времени обслуживания:
```
m₃ = ρ*q
```
Для системы массового обслуживания с отказами m₃ можно найти по формуле:
```
     m
m₃ = ∑(n * P_n)
    n=1
```
Общее количество требований, находящихся в системе (М). Эту величину определяют следующим образом:
- система массового обслуживания с отказами:
```
M = m₃
```
- система массового обслуживания с ограниченной длиной очереди и ожиданием:
```
M = m₃ + M_ож
```
Среднее время ожидания требованиям начала обслуживания (Т_ож).

Если известна функция распределения вероятности времени ожидания требованиям начала обслуживания F(f) = P(T_ож < t), то среднее время ожидания находится как математическое ожидание случайной величины:
```
               ∞
T_ож = M[T_ож] = ∫(t dF)
               0
```
Т_ож при показательном законе распределения требований во входящем потоке можно определить по формуле:
```
Т_ож = M_ож / λ
```

Экономические показатели СМО

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

Одним из общих экономических показателей является экономическая эффективность:

E = P_обсл*λ*c*T - G_п

, где
  с - средний экономический эффект, полученный при обслуживании одного требования;
  Т - рассматриваемый интервал времени;
  G_п - величина потерь в системе.

Величину потерь можно определить по следующим формулам:

система с отказами:
```
G_п = (q_k * m₃ + q_y * P_отк * λ + q_пк * m_св)T
```
, где:
  q_k - стоимость эксплуатации одного прибора в единицу времени;
  q_y - стоимость убытков в результате ухода требований из системы в единицу времени;
  q_пк - стоимость единицы времени простоя прибора системы;
  m_св = m – m₃;
система с ожиданием:
```
G_п = (q_ож*M_ож + q_пк * m_св + q_k * m₃)T
```
, где q_ож - стоимость потерь, связанных с простоем требований в очереди в единицу времени.

Практический пример моделирования СМО

Давайте попробуем теперь смоделировать СМО (на примере работы банка)...

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

Имеется банк, в котором N касс. Клиенты приходят в банк с интервалом F1(N1, N2) минут. Каждый кассир обслуживает клиента в течение F2(N3, N4) минут. Все клиенты находятся в очереди. После того, как кассир обслужил клиента, он может заняться другим клиентом, находящимся в очереди первым. Через определенный промежуток времени (N5 минут) у каждого кассира имеется перерыв (продолжительность N6 минут). После окончания времени работы (T минут), все клиенты, которые находятся в банке, должны быть обслужены.

Здесь Fi(x, y) - некоторый закон распределения случайной велечины (может быть как равномерным, так и нормальным), зависящей от параметров x и y.

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

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

Для реализации модели использовался класс FIFO-очереди (TQueue), работающий с указателями на объект TClient (подробнее об этом объекте - чуть ниже):

Type
  T = PTClient;

  PTQueueItem = ^TQueueItem;
  TQueueItem = object
    item: T;
    next: PTQueueItem;

    constructor create(value: T);
  end;

  {
    Реализуются 2 основные операции - помещение в очередь (put), и извлечение из нее (get)
  }
  TQueue = object
    constructor create;
    destructor destroy;

    procedure get(var value: T);
    procedure put(const value: T);

    function is_empty: boolean;

  private
    front, back: PTQueueItem;
  end;

Реализация очереди не представляет собой ничего сверхъестественного, тем более вот здесь Очередь (FIFO: First In First Out) она уже рассматривалась, поэтому останавливаться на ней я не буду...

Кроме очереди нам понадобятся объекты еще 2-х типов, представляющие Клиента и Кассира.

Вот так выглядит Клиент:

type
  PTClient = ^TClient;
  TClient = object

    constructor create(value: integer);
    function get_id: integer;

  private
    ID: integer;
  end;

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

type
  status = (
    { состояние "занят: работаю с клиентом" }
    _busy = 0,
    { состояние: "свободен - жду очередного клиента" }
    _waiting,
    { состояние: "отдыхаю" }
    _vacation
  );

  PTCasher = ^TCasher;
  TCasher = object

    state: status;
    work_time, ID: integer; { *** const *** }
    working_time, this_client: integer;

  public
    constructor create(_id, _work: integer);
    { Функция Handle вызывается ежеминутно (по времени модели) из Менеджера, и возвращает текущее состояние
      кассира (как результат) и через параметр changed - признак того, что состояние изменилось }
    function handle(var changed: integer): status;
    
    { Эта функция просто напросто имитирует подход клиента к кассиру: переводит кассира в состояние
      "занят" и устанавливает время обслуживания данного клиента... }
    procedure next;
  end;

Еще один необходимый для нашей модели тип - Менеджер:

type
  TManager = object
    { Включает в себя очередь "посетителей" (Клиентов), массив "Кассиров" ... }
    queue: TQueue;
    cash_workers: array[0 .. pred(n)] of PTCasher;

    { ... текущее время (0 - при начале работы банка), и время после прихода последнего посетителя }
    current_time, after_prev_enter: integer;

  public
    constructor create;
    destructor destroy;

    procedure run;
  end;

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

Итак:

{ Константы и функции, задающие начальные условия }
const
  n  = 10;
  n5 =  6;
  n6 =  3;
  nT = 50;

{
  Для простоты реализации и понимания программы функции возвращают равномерно распределенные
  случайные числа, не зависящие от параметров; для идеального выполнения всех условий указанных
  в задаче, нужно заменить их на функции, генерирующие СВ по заданному закону распределения ...
}
function f1: integer;
begin
  f1 := random(4) + 2;
end;
function f2: integer;
begin
  f2 := random(10);
end;

(***** TClient *****)
type
  PTClient = ^TClient;
  TClient = object

    constructor create(value: integer);
    function get_id: integer;

  private
    ID: integer;
  end;

constructor TClient.create(value: integer);
begin
  ID := value;
end;
function TClient.get_id: integer;
begin
  get_id := ID;
end;


type
  T = PTClient;

  PTQueueItem = ^TQueueItem;
  TQueueItem = object
    item: T;
    next: PTQueueItem;

    constructor create(value: T);
  end;

  TQueue = object
    constructor create;
    destructor destroy;

    procedure get(var value: T);
    procedure put(const value: T);

    function is_empty: boolean;

  private
    front, back: PTQueueItem;
  end;



constructor TQueueItem.create(value: T);
begin
  item := value;
  next := nil;
end;

constructor TQueue.create;
begin
  front := nil; back := nil;
end;

destructor TQueue.destroy;
var value: T;
begin
  while not is_empty do get(value);
end;

procedure TQueue.get(var value: T);
var pt: PTQueueItem;
begin
  if is_empty then begin
    writeln('Trying to Get from the empty queue !'); halt(101)
  end;

  pt := front;
  front := front^.next;

  value := pt^.item;
  dispose(pt);
end;


procedure TQueue.put(const value: T);
var pt: PTQueueItem;
begin
  pt := new(PTQueueItem, create(value));
  if is_empty then begin
    front := pt; back := pt;
  end
  else begin
    back^.next := pt;
    back := pt;
  end;
end;


function TQueue.is_empty: boolean;
begin
  is_empty := (front = nil)
end;


type
  status = (
    _busy = 0, _waiting, _vacation
  );

  PTCasher = ^TCasher;
  TCasher = object

    state: status;
    work_time, ID: integer; { *** const *** }
    working_time, this_client: integer;

  public
    constructor create(_id, _work: integer);
    function handle(var changed: integer): status;
    procedure next;
  end;


constructor TCasher.create(_id, _work: integer);
begin
  ID := _id; work_time := _work; state := _waiting;

  working_time := work_time;
end;

{
  Функция Handle вызывается ежеминутно из Менеджера, и возвращает текущее состояние
  Кассира (как результат) и через параметр changed - признак того, что состояние изменилось
}
function TCasher.handle(var changed: integer): status;
begin
  changed := 0;

  { 
    Если кассир работал с Клиентом, то уменьшаем оставшееся время работы с ним,
    и одновременно уменьшаем счетчик времени до очередного отдыха Кассира
  }
  if state = _busy then begin
    dec(this_client);
    dec(working_time);

    {
      Если this_client = 0, это значит, что с этим Rлиентом мы закончили работать,
      статус изменился как минимум на "ожидание", кроме этого - устанавливаем признак
      того, что состояние изменилось
    }
    if this_client = 0 then begin
      state := _waiting; changed := 1;
    end;
  end;

  {
    Если Кассир отдыхал - то уменьшаем время отдыха (когда кассир начинает отдыхать,
    в переменную working_time записывается _отрицательное_ значение, и постепенно
    увеличивается, чтобы не вводить специальную переменную)
  }
  if state = _vacation then begin
    inc(working_time);
    
    {
      Если working_time = 0, то отдых закончился, и переходим в "ожидание",
      с установкой признака изменения состояния, и кроме этого, устанавливаем
      положительное время работы ДО следующего отдыха
    }
    if working_time > 0 then begin
      state := _waiting; working_time := work_time; changed := 1;
    end;
  end;

  {
    Если после всех предыдущих проверок состояние = "ожидание" ...
  }
  if state = _waiting then begin
  
    {
      ... если не было изменения состояния - уменьшаем время до очередного отдыха
      (если это условие не поставить, то время может уменьшится дважды - один раз при
      переходе от _busy к _waiting, и второй раз - здесь, а это делать нежелательно)
    }  
    if changed = 0 then dec(working_time);
    
    {
      ... и, наконец, проверяем не пришло ли время отдохнуть (это уже проверяется
      независимо от того, было ли изменение состояния, т.е. если кассир на этой минуте
      закончил работать с клиентом, и ему уже пора отдыхать, он должен начать отдыхать...),
      и если пришло, то ставим отрицательное время работы равное константе N6, и
      сигнализируем об изменении состояния
    }
    if working_time <= 0 then begin
      state := _vacation; working_time := -n6; changed := 1;
    end;
  end;

  handle := state;
end;

{
  Эта функция просто напросто имитирует подход клиента к кассиру: переводит кассира в
  состояние "занят" и устанавливает время обслуживания данного клиента...
}
procedure TCasher.next;
begin
  state := _busy;
  this_client := f2;
end;


type
  TManager = object
    { Менеждер включает в себя очередь "посетителей", массив "Кассиров" ... }
    queue: TQueue;
    cash_workers: array[0 .. pred(n)] of PTCasher;

    {
      ... текущее время (0 - при начале работы банка),
      и время после прихода последнего посетителя
    }
    current_time, after_prev_enter: integer;

  public
    constructor create;
    destructor destroy;

    procedure run;
  end;

constructor TManager.create;
var i: integer;
begin
  current_time := 0; after_prev_enter := 0;
  
  { инициализируем "Кассиров" }
  for i := 0 to pred(n) do
    cash_workers[i] := new(PTCasher, create(i + 1, n5));
end;

{
  В деструкторе - "закрываем кассы"
}
destructor TManager.destroy;
var i: integer;
begin
  for i := 0 to pred(n) do
    dispose(cash_workers[i]);
end;

{
  вот в этой функции как раз и происходит вся имитация:
}
procedure TManager.run;
const
  {
    эта _статическая_ переменная - для хранения количества пришедших
    посетителей (используется для присвоения ID клиенту)
  }
  client_entered: integer = 0;
var
  i: integer;
  status_changed: integer;
  curr_status: status;
  client: PTClient;
begin

  {
    Все операции продолжаются до тех пор, пока не вышло время работы банка,
    и потом, пока в очереди есть хотя бы один посетитель (не выгонять же, правда?)
  }
  while (current_time <= nT) or (not queue.is_empty) do begin

    { Перебираем всех кассиров, и для каждого ... }
    for i := 0 to pred(n) do begin
    
      { предполагаем, что его статус НЕ изменился }
      status_changed := 0;
      
      { получаем статус кассира обращением к ЕГО методу }
      curr_status := cash_workers[i]^.Handle(status_changed);

      {
        если статус изменился - отобразить этот факт в статистике (какой кассир,
        как изменился статус, когда изменился - в какое время)
      }
      if status_changed <> 0 then { statistics }
        case curr_status of
          _vacation:
            writeln('casher #', i, ' goes to rest at:: ', current_time);
          _waiting:
            writeln('casher #', i, ' awaiting at:: ', current_time);
        end;

      { если сейчас проверяемый кассир ожидает клиента, то ... }
      if curr_status = _waiting then
        if not queue.is_empty then begin

          { ... вытянуть посетителя из очереди (если там кто-то есть, разумеется) }
          queue.get(client);
          {
            добавить в статистику, что такой-то посетитель направлен к такому-то
            кассиру в такое-то время
          }
          writeln('client #', client^.get_id, ' sent to casher #', i, ' at:: ', current_time);
          
          { и, собственно, направить клиента к кассиру }
          cash_workers[i]^.next;
          dispose(client);

        end;

    end;

    {
      здесь (после каждого прохода по всем кассирам) проверяем,
      не закончилось ли время работы банка ...
    }
    if current_time <= nT then begin

      {
        если еще НЕ закончилось - то увеличиваем время, прошедшее
        после прихода последнего посетителя
      }
      inc(after_prev_enter);
      
      {
        и если это время больше того, которое должно быть по формуле
        (интервал между приходом посетителей)
      }
      if after_prev_enter > f1 then begin

        {
          то имитируем приход очередного клиента: он только что пришел,
          т.е. время обнуляем ...
        }
        after_prev_enter := 0;
        inc(client_entered);
        
        {
          вызываем конструктор TClient, перед этим увеличиваем общий счетчик посетителей,
          и передаем его значение как ID в конструктор (чтобы ВСЕ посетители хоть чем-то
          различались)
        }
        client := new(PTClient, create(client_entered));
        
        { добавляем вновь прибывшего посетителя в очередь }
        queue.put(client);

      end;
      
      {
        если же время работы банка уже закончилось, то новые посетители НЕ будут добавляться
        в очередь, а те, кто пришел раньше, и уже стоит в очереди, будут обслужены, и только
        тогда этот цикл закончится...
      }

    end;
    { прибавляем к "банковскому" времени минуту, и начинаем заново опрашивать кассиров }
    inc(current_time);
  end;
  writeln(client_entered);

end;

var bank: TManager;
begin

  bank.create;
  bank.run;
  bank.destroy;
end.

Исходник: bank.pas