Задачи целочисленного программирования. Метод Гомори. 8 страница

7. аудиторские фирмы;

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

9. телефонные станции;

10. железнодорожные станции и т.д.

Основными компонентами системы массового обслуживания любого вида являются:

1. входной поток поступающих требований или заявок на обслуживание;

2. дисциплина очереди;

3. механизм обслуживания.

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

Чаще всего используются дисциплины очереди, определяемые следующими правилами:
- первым пришел – первый обслуживаешься;
- пришел последним — обслуживаешься первым;
- случайный отбор заявок;
- отбор заявок по критерию приоритетности;
- ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что вполне и полностью ассоциируется с понятием «допустимая длина очереди»).
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продол­жительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процеду­ры.

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

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

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

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

2. вероятностным распределением времени продолжительности обслуживания;

3. конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);

4. количеством и производительностью обслуживающих каналов;

5. дисциплиной очереди;

6. мощностью и возможностями источника требований.

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

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

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

3. относительная и абсолютная пропускная способность системы;

4. средний процент заявок, получивших отказ в обслуживании;

5. среднее время ожидания в очереди;

6. средняя длина очереди;

7. средний доход от функционирования системы в единицу времени и тому подобное.

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

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

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

- СМО, содержащее один канал обслуживания, называется одноканальной.

- СМО содержащее более одного канала обслуживания – многоканальной.

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

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

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

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

Если в СМО отсутствует приоритет, то заявки отбираются из очереди в канал по различным правилам например;

· Первым пришел – первым обслужен (FCFS – First Came – First Served)

· Последним пришел – первым обслужен (LCFS – Last Came – First Served)

· Первоочередное обслуживание требований с кратчайшей длительностью обслуживания (SPT/SJE)

· Первоочередное обслуживание требований с кратчайшей длительностью дообслуживания (SRPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью обслуживания (SEPT)

· Первоочередное обслуживание требований с кратчайшей средней длительностью дообслуживания (SERPT)

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

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

Чаще всего СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

– число каналов в СМО;

– интенсивность поступления в СМО заявок;

– интенсивность обслуживания заявок;

– коэффициент загрузки СМО;

– число мест в очереди;

– вероятность отказа в обслуживании поступившей в СМО заявки;

– вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

При этом:

(39)

А – среднее число заявок, обслуживаемых в СМО в единицу времени (абсолютная пропускная способность СМО)

(40) – среднее число заявок, находящихся в СМО

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

, (41) где – вероятность нахождения системы в S_k состоянии.

– коэффициент занятости каналов

– среднее время ожидания заявки в очереди

– интенсивность ухода заявок из очереди

– среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

(42) Где – вероятность нахождения в очереди i заявок;

– среднее время пребывания заявки с СМО

– среднее время пребывания заявки в очереди

В открытых СМО справедливы соотношения:

(43)

(44)

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

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

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

Рисунок 87. – Граф состояний одноканальной СМО

Здесь и – интенсивность потока заявок и выполнения заявок. Состояние системы S_o обозначает, что канал свободен, а S₁ – что канал, соответственно, занят обслуживанием заявки.

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

Рисунок 88.

где p_o(t) и p₁(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p_o и p₁ получим, приравнивая к нулю производные в первых двух уравнениях системы. В результате получим:

Рисунок 89.

Вероятность p₀ по своему смыслу - это вероятность обслуживания заявки p_обс, так как канал является свободным, а вероятность р₁ - по своему смыслу является вероятностью отказа, в обслуживании поступающей в СМО заявки р_отк, так как, канал занят обслуживанием предыдущей заявки.

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

Рисунок 90 – Граф состояний многоканальной СМО с отказами

Состояние S_0, естественно, означает, что все каналы свободны, состояние S_k (k = 1, n) означает, что обслуживанием заявок заняты k каналов.

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

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

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

(45) При этом для нахождения финальных вероятностей можно воспользоваться вышеизложенными формулами (формулы Литтла). С их учётом получим:

(46) (47)

Эти формулы (46) и (47) называются формулами Эрланга – еще одного основателя теории массового обслуживания.

Вероятность отказа в обслуживании заявки р_отк равна вероятности того, что все каналы заняты, то есть система находится в состоянии S_n. Таким образом,

(48)

Относительную пропускную способность СМО можно найти:

(49)

Абсолютную пропускную способность можно найти:

(50)

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

(51)

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 91.

S0

Рисунок 91. – Граф состояний одноканальной СМО с ограниченной очередью

Состояния СМО представляются следующим образом:

S₀ – канал обслуживания свободен,

S₁ – канал обслуживания занят, но очереди нет,

S₂ – канал обслуживания занят, в очереди одна заявка,

S_k+1 – канал обслуживания занят, в очереди k заявок,

S_m+1 – канал обслуживания занят, все m мест в очереди заняты.

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

(52)

(53)

(54)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (54) и (53) с учётом (52). В результате получим:

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии S_m+1, то есть вероятность отказа в обслуживании заявки равна:

(55)

(56)

Таким образом относительная пропускная способность СМО равна:

(57)

Тогда абсолютная пропускная способность равна:

(58)

Ну и среднее число заявок, стоящих в очереди L_оч, находится по формуле

(59)

и может быть записано в виде:

(60)

При формула принимает вид:

(61)

– среднее число заявок, находящихся в СМО, находится по формуле 62.

(62)

и тогда может быть записано в виде:

(63)

При , получим:

(64)

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

Граф такой СМО изображён на рисунке.

Рисунок 92. – Граф состояний одноканальной СМО с неограниченной очередью

Все характеристики такой СМО можно получить из вышеизложенных формул, полагая в них . При этом необходимо различать два существенно разных случая то есть: а) ; б) . В первом случае, как это видно из формул (22), (23), р₀ = 0 и p_k = 0 (при всех конечных значениях k). Это означает, что при очередь естественно неограниченно возрастает, то есть этот случай практического интереса не представляет.

Рассмотрим случай, когда . Формулы при этом запишутся в виде:

(65)

(66)

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

(67)

Тогда абсолютная пропускная способность равна:

(68)

А среднее число заявок в очереди получим из формулы при :

(69)

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

(70)

Среднее число заявок, находящихся в СМО:

(71)

Ну и среднее время пребывания заявки в СМО и в очереди определяются этими формулами.

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

Граф такой системы представлен на рисунке 93.

Рисунок 93. – Граф состояний многоканальной СМО с ограниченной очередью

– все каналы свободны, очереди нет;

– заняты l каналов (l = 1, n), очереди нет;

- заняты все n каналов, в очереди находится i заявок (i = 1, m).

Сравнение графов на рисунке 89 и рисунке 93 показывает, что последняя система является частным случаем системы размножения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):

Рисунок 94.

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

Рисунок 95.

Тогда образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, то есть в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Так как эти события несовместны, то вероятность образования очереди p_оч равна сумме соответствующих вероятностей :

(72)

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

(73)

Относительная пропускная способность равна:

(74)

Абсолютная пропускная способность:

(75)

Среднее число заявок, находящихся в очереди, определяется по формуле (71) и может быть записано в виде:

(76)

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

(77)

Среднее число заявок, находящихся в СМО:

(78)

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

Граф такой СМО изображен на рисунке 96 и получается из графа на рисунке 7 при .

Рисунок 96 – Граф состояний многоканальной СМО с неограниченной очередью

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при . При этом следует иметь в виду, что при вероятность р₀ = р₁=…= p_n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай . При из этого получим:

(79)

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

(80)

Из вышеизложенных формул получим выражение для вероятности образования очереди заявок:

(81)

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

(82)

Относительная пропускная способность:

(83)

Абсолютная пропускная способность:

(84)

Из формул при получим выражение для среднего числа заявок в очереди: