Рефераты, курсовые и дипломы на заказ без предоплаты.  Антиплагиат.
Студенточка.ru: на главную страницу.  рефераты, курсовые, дипломы на заказ без предоплаты в кратчайшие сроки  скидки и гарантии
Рефераты, курсовые, дипломные работы на заказ. Антиплагиат. Скидки
Прайс-лист Готовые работы Бесплатные материалы
ЗАКАЗАТЬ Специальности Банк рефератов
Консультации Статьи Подбор литературы
Готовые рефераты, курсовые и дипломы без предоплаты. Антиплагиат.
ЭКСПРЕСС - ЗАКАЗ:  для тех, кто экономит время и деньги при оформлении реферата,  курсовой, диплома на заказ

Внимание:

Мошенники используют скайп live:yagaya_baba и киви кошелек 9198012293, представляясь клиентам нашей компанией.

Студенточка не имеет никакого отношения к этим людям. С 15.05.2014 мы прекращаем консультации клиентов по скайпу и ICQ. Общение с клиентами возможно только по почте с домена studentochka.ru и телефону +7 916 812-22-59 или +7 926 206-99-13

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

Поиск материалов

Система массового обслуживания с ожиданием

Теория массового обслуживания

Введение

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

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

Изобразим данную систему графически (рис. 1). Здесь кружочек 1 - обслуживающий прибор, треугольник - накопитель, кружочек О - источник требований. Требование, возникающее в источнике в момент окончания фиктивной операции «ожидания требований», поступает в накопитель. Если в этот момент прибор 1 свободен, то требование немедленно поступает на обслуживание. Если же прибор занят, то требование остается в накопителе, становясь в конец имеющейся очереди.

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

Система массового обслуживания с ожиданием

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

Мы изучим здесь классическую задачу теории массового обслуживания в тех условиях, в каких она была рассмотрена и решена Эрлангом. На m одинаковых приборов поступает простейший поток требований интенсивности ?. Если в момент поступления требования имеется хотя бы один свободный прибор, оно немедленно начинает обслуживаться. Если же все приборы заняты, то вновь поступившее требование становится в очередь за всеми теми требованиями, которые поступили раньше и еще не начали обслуживаться. Освободившийся прибор немедленно приступает к обслуживания очередного требования, если только имеется очередь. Каждое требование обслуживается только одним прибором, и каждый прибор обслуживает в каждый момент не более одного требования. Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F (x). Предполагается, что при

x ? 0

F (x) = 1 - e-?x, (1)

где ? > 0 - постоянная.

Эрланг решил эту задачу, имея в виду постановки вопросов возникших к тому времени в телефонном деле.

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

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

Действительно, пусть fa (t) означает вероятность того, что обслуживание, которое уже продолжается время a, продлится еще не менее чем t. В предположении, что длительность обслуживания распределена показательно, f0 (t) =e-?t. Далее ясно, что f0 (a) = e-?a и f0 (a+t) = e-? (a+1). А так как всегда f0 (a+t) = f0 (a) fa (t), то e-? (a+t) = e-?a f0 (t) и, следовательно,

fa (t) = e-?t = fo (t).

Требуемое доказано.

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

где, ? > 0, а k - целое положительное число.

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

Обозначим для случая распределения (1) через ? время обслуживания требования. Тогда средняя длительность обслуживания равна

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

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

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

Найдём те уравнения, которым удовлетворяют вероятности Pk (t). Одно из уравнений очевидно, а именно для каждого t

. (2)

Найдем сначала вероятность того, что в момент t+h все приборы свободны. Это может произойти следующими способами:

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

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

Остальные возможности, как-то: были заняты два или три прибора и за время h работа на них была закончена - имеют вероятность o (h), как легко в этом убедится.

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

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

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

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

(3)

Перейдем теперь к составлению уравнений для Pk (t) при k ? 1. Рассмотрим отдельно два различных случая: 1 ? k ? m и k ? m. Пусть вначале 1 ? k ? m. Перечислим только существенные состояния, из которых можно прийти в состояние Ek в момент t+h. Эти состояния таковы:

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

В момент t система находилась в состоянии Ek-1, за время h поступило новое требование, но ни одно ранее находившееся требование не было закончено обслуживанием. Вероятность этого события равна

В момент t система находилась в состоянии Ek+1, за время h новых требований не поступило, но одно требование было обслужено. Вероятность этого равна

Все остальные мыслимые возможности перехода в состояние Ek за промежуток времени h имеют вероятность, равную 0 (h).

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

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

(4)

Подобные же рассуждения для k ? m приводят к уравнению

' (5)

Для определения вероятностей Pk (t) мы получили бесконечную систему дифференциальных уравнений (2) - (5). Ее решение представляет несомненные технические трудности.

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

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

Сказанное позволяет заключить, что уравнения (3), (4) и (5) для стационарных вероятностей принимают следующий вид:

(6)

при 1 ? k ? m

(7)

при k ? m

(8)

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

(9)

Для решения полученной бесконечной алгебраической системы введем обозначения: при 1? k?m

при k ? m

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

z1=0, zk-zk+1=0 при k ? 1

Отсюда заключается, что при всех k ? 1 zk =0

т. е. при 1 ? k ? m

k?Pk=?Pk-1 (10)

и при k ? mm?Pk=?Pk-1 (11)

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

?=?/?.

Уравнение (10) позволяет заключить, что при 1 ? k ? m

(12)

При k ? m из уравнения (11) находим, что

и следовательно, при k ? m

(13)

Остается найти P0. Для этого в (9) подставляем выражения Pk из (12) и (13). В результате

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

? ? m (14)

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

(15)

Если условие (14) не выполнено, т. е. если ? ? m, то ряд, стоящий в квадратной скобке уравнения для определения P0, расходится и, значит, P0 должно быть равно 0. Но при этом, как следует из (12) и (13), при всех k ? 1 оказывается Pk =0.

Методы теории цепей Маркова позволяют заключить, что при ? ? m с течением времени очередь стремится к ? по вероятности.

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

Во введении мы уже говорили, что для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания. Длительность ожидания представляет собой случайную величину, которую обозначим буквой ?. Рассмотрим сейчас только задачу определения распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания. Обозначим далее через P?? ? t? вероятность того, что длительность ожидания превзойдет t, и через Pk?? ? t? вероятность неравенства, указанного в скобке, при условии, что в момент поступления требования, в очереди уже находится k требований. В силу формулы полной вероятности имеем равенство

P?? ? t?=. (16)

Прежде чем преобразовать эту формулу к виду, удобному для пользования, приготовим некоторые необходимые нам для дальнейшего сведения. Прежде всего для случаев m=1 и m=2 найдем простые формулы для P0. несложные преобразования приводят к таким равенствам: при m=1

P0=1-?, (17)

а при m=2

(18)

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

(19)

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

?=?, (20)

при m=2

(21)

Напомним, что в формуле (19) ? может принимать любое значение от 0 до m (включительно). Так что в формуле (20) ? ? ?, а в (21) ? ? 2.

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

Если в момент поступления требования в очереди уже находились k-m требований, то поскольку обслуживание происходит в порядке очередности, вновь поступившее требование должно ожидать, когда будут обслужены k-m+1 требований. Пусть qs (t) означает вероятность того, что за промежуток времени длительности t после поступления интересующего нас требования закончилось обслуживание ровно требований. Ясно, что k ? m имеет место равенство

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

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

Итак,

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

Но вероятности Pk известны:

поэтому

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

Из формул (13) и (19) следует, что, поэтому при t>0

(22)

Само собой разумеется, что при tФункция имеет в точке t=0 разрыв непрерывности, равный вероятности застать все приборы занятыми.

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

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

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

(23)

Дисперсия величины ? равна

.

Формула (23) дает среднюю длительность ожидания одного требования. Найдем среднюю потерю времени требованиями, пришедшими в систему обслуживания в течение промежутка времени T. За время T в систему поступает ?T требований в среднем; общая потеря ими времени на ожидание в среднем равна

(24)

Приведем небольшие арифметические подсчеты, которые продемонстрируют нам, как быстро возрастают суммарные потери времени на ожидание с изменением величины ?. При этом мы ограничиваемся случаем T=1 и рассматриваем лишь самые малые значения m: m=1 и m=2.

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

При ?=0. 1; 0. 3; 0. 5; 0. 9; значение ?? приблизительно равно 0. 011; 0. 267; 0. 500; 1. 633; 8. 100.

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

При ?=0. 1; 1. 0; 1. 5; 1. 9 значение ?? приблизительно равно 0. 0003; 0. 333; 1. 350; 17. 587.

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

Приложение теории к движению воздушного транспорта

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

Допустим, что самолеты приближаются к зоне управления со случайных направлений через случайные промежутки времени, распределенные по экспоненциальному закону, с постоянной интенсивностью прибытия, которая принимается равной одной единице. Следовательно, e-t - распределение промежутков времени между моментами прибытия. Самолет, который прибывает через промежуток времени, меньший минимального времени, необходимо для безопасного предыдущего самолета, задерживается на минимальное время. Отношение минимального времени, необходимого для безопасной посадки, к средней длительности промежутка времени между прибывающими самолетами обозначается T (для простоты будем считать, что для данного аэропорта эта величина постоянна). Обычно представляет интерес случай T(14. 54)

Вероятность того, что будет задержан один самолет, найдем, рассмотрев все задержки одиночных самолетов между двумя незадерживаемыми самолетами. Самолет, который будет задержан, должен прибыть через промежуток времени t12T-t1. Таким образом, искомая вероятность совместного появления этих двух событий равна

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

t1 t2 t В результате для двух задерживаемых самолетов получаем

. (14. 55)

Общее выражение для вероятности того, что задерживается n-1 самолетов, имеет вид ?n Tn-1 e-nT, где ?n- коэффициент, зависящий только от n. Очевидно, что должно выполняться соотношение

(14. 56)

или

(14. 57)

где величина U?Te-T для малых T определяется однозначно, следовательно, T можно выразить как функцию от U:

(14. 58)

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

(14. 59)

Следовательно, разложив подынтегральное выражение в ряд и выбрав коэффициент при T-1, можно найти вычет.

Вероятность того, что один за другим задерживаются n-1 самолетов, равна

(14. 60)

Используя формулу Стирлинга для n?, Пирси приводит ряд кривых для этого распределения.

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

(14. 61)

Это выражение можно легко найти, дифференцируя выражение (14. 56) по T и производя упрощения. (Заметим, что при T=1 задерживаются все самолеты). Аналогично находим второй начальный момент, он равен.

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

.

Распределение длительности посадки найдем путем следующих рассуждений. Все промежутки времени длительностью tT, появляется с частотой 1-T появления незадерживаемых самолетов, умноженной на вероятность их прибытия, т. е. на e- (t+T). Используем единичную функцию H (T- t) (которая равна единице для положительных значений аргумента и равна нулю для отрицательных; ее производная является дельта-функцией) и дельта-функцию ? (T-t), чтобы представить это распределение в виде

Теперь, используя интегральное уравнение Линдли, можно получить распределение времени ожидания. Путем детального анализа Пирси находит выражение для распределения в промежутке времени t, mT

откуда после интегрирования по t (? ? t ? ?) он определяет T как долю задерживаемых самолетов. Заметим, что при суммировании по m необходимо рассматривать интервалы (mT, (m+1) T). Отсюда находим также среднее время ожидания

.

Заметим, что время ожидания увеличивается с ростом T. Приведенное выше распределение дает критерии для определения необходимой пропускной способности аэропорта.

Список литературы

Д. Кениг, Д. Штойян. Методы теории массового обслуживания: Пер. с нем. /Под. ред. Г. П. Климова. М., 1981.

Г. И. Ивченко, В. А. Каштанов, И. Н. Коваленко. Теория массового обслуживания. М., 1982.

Б. В. Гнеденко, И. Н. Коваленко. Введение в теорию массового обслуживания. М., 1987.

Т. Л. Саати. Элементы теории массового обслуживания и ее приложения: Пер. с англ. /Под. ред. И. Н. Коваленко, изд-ие 2. М., 1971.


Описание предмета: «Теория массового обслуживания»

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

На первичное развитие теории массового обслуживания оказали особое влияние работы датского ученого А.К. Эрланга (1878-1929).

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

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

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

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

Литература

  1. В.И. Варфоломеев, С.В. Назаров. Алгоритмическое моделирование элементов экономических систем. Практикум. – М.: Финансы и статистика, 2004. – 264 с.
  2. Л.С. Крохин. Экономико-математические методы в оперативном управлении на транспорте. – М.: ВИНИТИ РАН, 2009. – 252 с.
  3. О.А. Сдвижков. Дискретная математика и математические методы экономики с применением VBA Excel. – М.: ДМК Пресс, 2012. – 212 с.
  4. Т.Л. Партыка, И.И. Попов. Математические методы. – М.: Форум, Инфра-М, 2007. – 464 с.
  5. Э.К. Алгазинов, А.А. Сирота. Анализ и компьютерное моделирование информационных процессов и систем. – М.: Диалог-МИФИ, 2009. – 416 с.
  6. В.П. Невежин, С.И. Кружилов, Ю.В. Невежин. Исследование операций и принятие решений в экономике. – М.: Форум, 2012. – 400 с.
  7. Владимиров Александр Федорович. Теории Случайных Функций,Марковских Процессов,Массового Обслуживания, Надежности И Восстановления В Приложении К Технической Эксплуатации Автомобилей. – М.: , 2006. – 1 с.
  8. А.П. Кирпичников. Прикладная теория массового обслуживания. – М.: Издательство Казанского университета, 2008. – 118 с.
  9. А.И. Ящура. Система технического обслуживания и ремонта промышленных зданий и сооружений. Справочник. – М.: НЦ ЭНАС, 2009. – 312 с.
  10. А.Я. Хинчин. Работы по математической теории массового обслуживания. – М.: Либроком, 2010. – 240 с.
  11. Б.В. Гнеденко. Беседы о теории массового обслуживания. – М.: Либроком, 2010. – 72 с.
  12. Ю.И. Неймарк. Динамические системы и управляемые процессы. – М.: Либроком, 2010. – 338 с.
  13. Т.Л. Саати. Элементы теории массового обслуживания и ее приложения. – М.: Либроком, 2010. – 520 с.
  14. В.А. Ивницкий. Теория нестационарных моментов марковских сетей. Разомкнутые сети массового обслуживания. – М.: Либроком, 2011. – 410 с.
  15. В.А. Ивницкий. Теория нестационарных моментов марковских сетей. Замкнутые сети массового обслуживания. – М.: Либроком, 2010. – 400 с.
  16. Головин Юрий Алексеевич. Российские Литературно-Художественные Журналы В Системе Массовой Коммуникации: Тезисы. – М.: , 2010. – 1 с.
  17. Й.Керстан, К.Маттес, Й.Мекке. Безгранично делимые точечные процессы. – М.: Главная редакция физико-математической литературы издательства "Наука", 1982. – 386 с.


Готовые работы

Тема работыТип работы
Реструктуризация банковской системы. Операции банков с драгоценными металлами
Банковский менеджмент
Курсовая работа
24 стр. / 2500 руб.
Кредитно-банковская система России
Финансы и кредит
Курсовая работа
27 стр. / 2800 руб.
Современная российская система налогообложения
Налогообложение
Диплом
103 стр. / 10700 руб.
Управление и собственность и их взаимосвязь
Менеджмент
Курсовая работа
30 стр. / 2900 руб.



Задайте свой вопрос по вашей работе

Крестьянова Марина Михайловна

marina@studentochka.ru
+7 916 812-22-59 с 9 до 21 ч. по Москве.






Добавить файл к заказу

- осталось написать email или телефон

Внимание!

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

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

Контакты
marina@studentochka.ru
+7 916 812-22-59
с 9 до 21 ч. по Москве.
Карта сайта ЗАКАЗАТЬ
Цены, скидки и акции
Реферат, доклад, эссе, контрольная 110 р./стр.
Курсовая от 120 р./стр.
Отчёт по практике 125 р./стр.
ВКР, дипломная от 175 р./стр.
Скидки. Антиплагиат.
Поделиться
Реклама


Реклама на сайте
Мы в социальных сетях
Отзывы
Наталья, 6.06
Я все получила, большое спасибо. Это то что надо.


Букинистика: редкие книги!

Рассылка 'Как написать отличный реферат, курсовую, диплом?'