реферат скачать
 

Классификация систем массового обслуживания и их основные элементы

Распределение Эрланга представляет собой распределение суммы k-

независимых слагаемых, каждое из которых имеет распределение (1).

Обозначим для случая распределения (1) через [pic] время обслуживания

требования. Тогда средняя длительность обслуживания равна

[pic]

Это равенство даст нам cпособ оценки параметра [pic] по опытным данным. Как

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

[pic]

2. Процесс обслуживания как марковский случайный процесс.

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

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

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

простоту. Теперь отметим более принципиальное соображение, которое станем

развивать применительно к изучаемой задаче.

В каждый момент рассматриваемая система может находиться в одном из

следующих состоянии: в момент t в системе находятся k требовании (k=0, 1,

2, ...). Если k[pic]rn, то в системе находятся и обслуживаются k

требований, а m-k - приборов свободны. Если k[pic]m, то m требований

обслуживаются, а k-m находятся в очереди и ожидают обслуживания. Обозначим

через [pic] состояние, когда в системе находятся k требований. Таким

образом, система может находиться в состояниях [pic] ... Обозначим через

[pic] — вероятность того, что система в момент t окажется в состоянии

[pic].

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

сделанных предположениях. Пусть в некоторый момент [pic] наша система

находилась и состоянии [pic]. Докажем, что последующее течение процесса

обслуживания не зависит в смысле теории вероятностей от того, что

происходило до момента [pic]. Действительно, дальнейшее течение

обслуживания полностью определяется тремя следующими факторами:

моментами окончания обслуживаний, производящихся в момент [pic];

моментами появления новых требований;

длительностью обслуживания требований, поступивших после [pic].

В силу особенностей показательного распределения длительность остающейся

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

обслуживание до момента [pic]. Так как поток требований простейший, то

прошлое не влияет на то, как много требований появится после момента [pic].

Наконец длительность обслуживания требований, появившихся после [pic],

никак не зависит от того, что и как обслуживалось до момента [pic].

Известно, что случайные процессы, для которых будущее развитие зависит

только от достигнутого в данный момент состояния и не зависит от того, как

происходило развитие в прошлом, называются процессами Маркова или же

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

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

случайный процесс Маркова. Это обстоятельство облегчает дальнейшие

рассуждении.

3. Составление уравнений.

Задача теперь состоит в том, чтобы найти те уравнения, которым

удовлетворяют вероятности [pic]. Одно из уравнения очевидно, a именно для

каждого t

[pic] (2)

Найдём сначала вероятность того, что и момент t.+h все приборы

свободны. Это может произойти следующими способами:

в момент t все приборы были свободны и за время h новых требований не

поступало;

в момент t один прибор был занят обслуживанием требования, все остальные

приборы свободны; за время h обслуживание требования было завершено и новых

требований не поступило.

Остальные возможности, как-то: были заняты два или три прибора и за

время h работа на них біла закончена - имеют вероятность о(h), как легко в

этом убедится.

Вероятность первого из указанных событий равна

[pic],

вероятность второго события

[pic].

Таким образом

[pic].

Отсюда очевидным образом приходим уравнению

Перейдём теперь к составлению уравнений для [pic] при [pic]1.

Рассмотрим отдельно два различных случая: 1[pic] и [pic]. Пусть в начале

1[pic]. Перечислим только существенные состояния, из которых можно прийти в

состояние [pic] в момент t+h. Эти состояния таковы:

В момент t система находилась в состоянии [pic], за время h новых

требований не поступило и ни один прибор не окончил обслуживания.

Вероятность этого события равна:

[pic]

В момент t система находилась в состоянии [pic], за время h поступило

новое требование, но ни одно ранее находившееся требование не было

закончено обслуживанием. Вероятность этого события равна

[pic]

В момент t система находилась в состоянии [pic], за время h новых

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

этого равна

[pic] Все остальные мыслимые возможности перехода в состояние [pic] за

промежуток времени h имеют вероятность, равную о(h).

Собрав воедино найденные вероятности, получаем следующее равенство:

[pic] Несложные преобразования приводят от этого равенства к такому

уравнению для 1[pic];

[pic] (4)

Подобные же рассуждения для [pic] приводят к уравнению

[pic] (5)

Для определения вероятностей [pic] получили бесконечную систему

дифференциальных уравнений (2)-(5). Её решение представляет несомненные

технические трудности.

4. Определение стационарного решения.

В теории массового обслуживания обычно изучают лишь установившееся решение

для [pic]. Существование таких решений устанавливается так называемыми

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

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

стационарные вероятности существуют. Введём для них обозначения [pic].

Заметим дополнительно, что [pic] при [pic].

Сказанное позволяет заключить, что уравнения (3), (4), (5) для

стационарных вероятностей принимают следующий вид:

[pic] (6)

при 1[pic]

[pic] (7)

при [pic]

[pic] (8)

К этим уравнениям добавляется нормирующее условие

[pic] (9)

Для решения полученной бесконечной алгебраической системы введём

обозначения: при 1[pic]

[pic]

при [pic]

[pic]

Система уравнений (6)-(8) в этих обозначениях принимает такой вид:

[pic] [pic] при [pic]

Отсюда заключаем, что при всех [pic]

[pic]

т.е. при 1[pic]

[pic] (10)

и при [pic]

[pic] (11)

Введём для удобства записи обозначение

[pic].

Уравнение (10) позволяет заключить, что при 1[pic]

[pic] (12)

При [pic] из (11) находим, что

[pic]

и, следовательно, при [pic]

[pic] (13)

Остаётся найти [pic]. Для этого в (9) подставляем выражения [pic] из

(12) и (13). В результате

[pic]

так как бесконечная сумма, стоящая в квадратных скобках, сходится

только при условии, что

[pic] (14)

то при этом предположении находим равенство

[pic] (15)

Если условие (14) не выполнено, т.е. если [pic], то ряд, стоящий в

квадратной скобке уравнения для определения [pic], расходится и, значит,

[pic] должно быть равно 0. Но при этом, как следует из (12) и (13), при

всех [pic] оказывается [pic].

Методы теории цепей Маркова позволяют заключить, что при [pic] с

течением времени очередь стремится к [pic] по вероятности.

Поясним полученный результат на нескольких практических примерах,

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

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

специфика случайных колебаний в поступлении требований на обслуживание,

приводят к серьезным просчетам.

Пусть врач успевает удовлетворительно осмотреть больного и заполнить

его историю болезни в среднем за 15 минут. Планирующие органы из этого

обычно делают вывод: за четырёхчасовый рабочий день врач должен принимать

16 человек. Однако больные приходят в случайные моменты времени. В

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

скапливается очередь, так как при проведенном подсчете [pic] принимается

равным 1. Те же заключения относятся и к расчету числа коек в больницах,

числа работающих касс в магазинах, числа официантов в ресторанах и т. д. К

сожалению, некоторые экономисты совершают такую же ошибку и при расчете

погрузочных средств в карьерах, числе приемщиков на элеваторах, числе

причалов в морских портах и пр.

Во всем дальнейшем мы предполагаем, что условие (14) выполнено.

5. Некоторые подготовительные результаты.

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

является длительность ожидания требованием начала обслуживания.

Длительность ожидания представляет собой случайную величину, которую

обозначим буквой [pic]. Рассмотрим сейчас только задачу определения

распределения вероятностей длительности ожидания в уже установившемся

процессе обслуживания. Обозначим далее через [pic] вероятность того, что

длительность ожидания превзойдёт t, и через [pic] вероятность неравенства,

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

которого подсчитывается длительность ожидания, в очереди уже находится k

требований. В силу формулы полной вероятности имеем равенство

[pic] (16)

Прежде чем преобразовать эту формулу к виду, удобному для

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

Прежде всего для случаев m=1 и m=2 найдем простые формулы для [pic].

Несложные преобразования приводят к таким равенствам: при m=1

[pic]=1-[pic], (17)

а при m=2

[pic] (18)

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

то наудачу взятый момент. Очевидно, что эта вероятность равна

[pic] (19)

Эта формула для m=1 принимает особенно простой вид:

[pic] (20)

при m=2

[pic] (21)

В формуле (19) [pic] может принимать любое значение от 0 до m

(исключительно). Так что в формуле (20) [pic]< 1, а в (21) [pic]<2.

6. Определение функции распределения длительности ожидания.

Если в момент поступления требования в очереди уже находились k-m

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

вновь поступившее требование должно ожидать, когда будут обслужены k-m+1

требований. Пусть [pic] означает вероятность того, что за промежуток

времени длительности t после поступления интересующего требования

закончилось обслуживание ровно s требований. Ясно, что при [pic] имеет

место равенство

[pic]

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

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

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

требований, то вероятность за время t не завершить ни одного обслуживания

(т.е. вероятность того, что не освободится ни один из приборов) равна

[pic]

Если все приборы заняты обслуживанием и ещё имеется достаточная

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

требований будет простейшим. Действительно, в этом случае все три условия —

стационарность, отсутствие последействия и ординарность — выполнены.

Вероятность освобождения за промежуток времени t ровно s приборов равна

(это можно показать и простым подсчетом)

[pic]

Итак,

[pic]

и, следовательно,

[pic]

Но вероятности [pic] известны:

[pic]

поэтому

[pic]

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

виду

[pic][pic]=

[pic]

[pic][pic].

Из формул (18) и (19) следует, что [pic] поэтому при m[pic]0

[pic] (22)

Само собой разумеется, что при t[pic]0

[pic]

Функция [pic] имеет в точке t=1 разрыв непрерывности, равный

вероятности застать все приборы занятыми.

7. Средняя длительность ожидания.

Формула (22) позволяет находить все интересующие числовые

характеристики длительности ожидания. В частности, математическое ожидание

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

средняя длительность ожидания равна

[pic]

Несложные вычисления приводят к формуле

[pic] (23)

Дисперсия величины [pic] равна

[pic]

Формула (23) даёт среднюю длительность ожидания одного требования. Найдем

среднюю потерю времени требованиями, пришедшими в систему обслуживания в

течение промежутка времени T. За время T в систему поступает [pic]

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

[pic] (24)

Приведем небольшие арифметические подсчеты, которые продемонстрируют

нам, как быстро возрастают суммарные потери времени па ожидание с

изменением величины [pic]. При этом мы ограничиваемся случаем Т=1 и

рассматриваем лишь самые малые значения т: т=1 и т=2.

При т=1 в силу (20)

[pic]

При р=0,1; 0,3; 0,5; 0,9 значение а[pic] приблизительно равно 0,011; 0,267;

0,500; 1,633; 8,100.

При m=2 в силу (24)

[pic][pic]

При [pic]=0,1; 1,0; 1,5; 1,9 значение а[pic] приблизительно равно

00003; 0,333; 1,350; 17,537.

Приведённые данные иллюстрируют хорошо известный факт относительно

большой чувствительности систем обслуживания, уже достаточно сильно

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

значительное возрастание длительности ожидания. Этот факт обязательно

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

обслуживания.

Раздел ІІІ. Пример использования СМО с ожиданием

В городе имеется транспортное агентство для обслуживания населения.

Число заявок на обслуживание случайно и представлено выборкой 1.

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

представлено выборкой 2.

Определить :

1) оптимальное число автомашин в агентстве, выполняющих операции в течение

10 часов в день; полагая, что обслуживание одной заявки приносит доход в

20 грн, а простой автомашины приносит убыток 3,25 грн. в час.

2) 5-6 операционных характеристик, наиболее существенных для анализа работы

агентства.

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

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

машина с наименьшим номером.

Выборка 1 число заявок на перевозку за день =0,046229

Х1

={8;5;8;4;21;0;9;3;8;5;1;4;12;0;10;1;0;7;2;21;1;3;4;6;0;8;2;22;1;2;8;4;5;6;2

;6;

3;6;16;7;2;2;2;13;5;5;21;2;4;}

Выборка 2 Время обслуживания одной заявки в часах.

Х2 =

25,52,22,7,15,55,43,11,25,24,23,24,13,15,11,38,8,18,14,73,8,48,22,4,30,6,17,

12,23,112,10,45,4,32,123,39,59,19,5,12,5,7,74,57,10,35,12,28,11,16.

Прежде чем рассматривать транспортное агентство как СМО, необходимо

доказать, что мы имеем на это право.

Действительно, наше транспортное агентство обладает всеми присущими СМО

элементами.

Входящий поток - заявки на перевозку, есть очередь неограниченной длинны,

обслуживающими приборами являются автомашины, обслуженные заявки составляют

входящий поток.

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

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

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

Докажем это на сознательном уровне. Ординарность вытекает из следующих

соображений: две или более заявок вряд ли успеют в секунду в секунду

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

остальные будут вынуждены стать в очередь, к тому же одна машина

одновременно не станет заниматься двумя или более заявками.

Отсутствие после действия обуславливается тем что заказчик машины (на

обслуживание) вряд ли знает, сколько поступило заявок на обслуживание до

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

зависимо друг от друга.

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

один час в среднем постоянно.

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

Пуассоновское распределение.

Приведём критерий проверки распределения входящего потока требований

на соответствие пуассоновскому закону распределения.

Одним из признаков того, что случайная величина распределена по

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

случайной величины и дисперсии этой же случайной величины, то есть:

[pic]

В качестве оценки для математического ожидания обычно выбирают

выборочное среднее

[pic]

а в качестве оценки дисперсии - выборочную дисперсию:

[pic]

где n - объём выборки X1={[pic]};

N - объём вариационного ряда;

[pic] - частота [pic] в выборке Х1.

Проведём расчёты:

[pic]

[pic]

Найдём отношение:

[pic]((

Результаты проверки распределения входящего потока требований на

соответствие пуассоновскому закону распределения приведены в приложении 2

.

Применение непараметрического критерия А.Н.Колмогорова для проверки

статистических гипотез

Рассмотрим применение этого критерия для проверки гипотез о

соответствии теоретического распределения случайной величины -

эмпирическому, где случайная величина представлена выборкой Х2. И

продемонстрируем его применение для анализа распределения времени

обслуживания одного из каналов СМО.

Пусть нам задана выборка Х2=[pic] случайной величины [pic] ,которая

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

исследуемой системы массового обслуживания. Выборка Х2 имеет объём n=50.

Гипотеза Н заключается в том, что случайная величина [pic] имеет

показательное распределение с параметром [pic], т.е.

[pic],

где [pic] - оценка параметра показательного распределения [pic], которая

находится как обратная величина к исправленному среднему выборочному [pic]:

[pic], где [pic],

а [pic] - элемент выборки Х2, выражает чистое время обслуживания k-той

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

Находим оценку параметра [pic] для нашей выборки Х2,

[pic]

[pic][pic]

[pic]

[pic] Дальнейший этап исследования заключается в построении эмпирической

функции распределения [pic]. Для этой цели построим по выборке Х2

вариационный ряд [pic], где [pic] - строго упорядоченные, а каждому

значению [pic] отвечает соответствующая ему частота [pic], равная числу

повторений [pic] в выборке Х2, причем выполняется тождество:

[pic].

Тогда эмпирическую функцию распределения можно записать в виде:

[pic][pic]

После того, как эмпирическая функция распределения построена, можно

вычислить разности

[pic]

в точках [pic], и [pic] где [pic] - достаточно малое число, скажем [pic].

Теперь вычисляем [pic], [pic], [pic] , где

[pic]=[pic]{[pic]; [pic]}

Для автоматизации вычислений значений [pic], [pic], [pic]

использована вычислительная техника, результаты занесены в Приложение 2.

[pic]=[pic]{[pic]; [pic]}

Далее проводим проверку гипотезы. По найденному значению [pic]

проверяем гипотезу Н, сравнивая [pic] с величиной [pic]. Если

[pic][pic][pic], то гипотезу Н о том, что время обслуживания заявок

подчинено показательному закону с параметром [pic], можно считать не

противоречащей опытным данным. Если же, [pic][pic][pic], то гипотеза Н

отвергается.

Квантиль z находим по приближённой формуле:

[pic],

исходя из заданного уровня значимости [pic].

Получаем для [pic]=0,0005: z=1,358102.

В нашем случае

[pic]=[pic]

и, сравнивая полученные величины находим:

0,095922[pic]0,226350 т.е.

[pic][pic][pic].

Выводы: Можно утверждать, что для 0,05% уровня значимости [pic] гипотеза Н

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

параметром [pic]=0,034975, не противоречит опытным данным.

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

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

распределение, мы имеем право приступать к дальнейшему решению поставленной

задачи.

Расчёты

Средняя интенсивность поступления заявок на транспортировку:

[pic] =6 заявок в день, а так как транспортное агентство работает 10 часов

в день то [pic] = 0,6 заявок в час.

2. Среднее время обслуживания заявки.

[pic]

3. интенсивность выходящего потока[pic]

3. коэффициент загрузки системы [pic]

таким образом из условия [pic] принимает min количество автомашин [pic]

5. находим среднее время ожидания заявки [pic] при количестве

автомобилей в агентстве больше 17. [pic]

[pic]

[pic]

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

[pic]

6. находим убыток от простоя автомашин в день

[pic]

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

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

приносит доход в 20 грн. то из-за большого времени ожидания в день

агентство будет не дополучать:

[pic]

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

заявок. [pic]

Для определения оптимального числа автомашин в агентстве выполняющих

операции в течении 10 часов в день нужно найти. [pic]

ІІ. Важнейшими операционными характеристиками СМО с ожиданием являются:

1. среднее число свободных устройств [pic]

2. среднее число занятых устройств [pic]

3. вероятность того что все обслуживающие устройства заняты [pic]

4. вероятность того что все обслуживающие устройства свободны [pic]

5. средняя длинна очереди [pic]

6. среднее время ожидания начала обслуживания: [pic]

7. коэффициент простоя обслуживающих устройств: [pic]

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

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

свободная машина с наименьшим номером

[pic]

Результаты расчетов приведены в приложении 2.

ВЫВОДЫ

В этой курсовой работе раскрыты понятия приводящие к системе массового

обслуживания, а именно: обслуживание, обслуживает прибор система

обслуживания, система массового обслуживания.

Также описаны типичные элементы, из которых состоят системы

массового обслуживания (входящий поток, его описание и основные

особенности, очередь и ее дисциплина, обслуживающие приборы и особенности

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

Что касается практического задания, то рассмотренное в данной

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

заявок на обслуживание является простейшим (Пуассоновским), а время

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

доказано с помощью не параметрического критерия А.Н. Колмогорова.

Оптимальное число автомашин в агентстве, выполняющих операции в

течении 10 часов в день равно 18.

Страницы: 1, 2


ИНТЕРЕСНОЕ



© 2009 Все права защищены.