Реферат: Системы с ожиданием - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Системы с ожиданием

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 77 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

Системы с ожиданием Введение Судьбу требований , которые при поступлении в систему обслуживания застают все приборы занятыми , определяют с помощью задания типа системы обслуживания . Один из типов систем является система с ожиданием. Системы с ожиданием - возможно ожидание для любого числа требований , которые не могут быть обслужены сразу . Они составляют очередь , и с помощью некоторой дисциплины обслуживания определяются , в каком порядке ожидающие требования выбираются из очереди для обслуживания. Изобразим данную систему г рафически (рис . 1). Здесь кружочек 1 - обслуживающий прибор , треугольник - накопитель , кружочек О - источник требований . Требование , возникающее в источнике в момент окончания фиктивной операции “ожидания требований” , поступает в накопитель . Если в этот м о мент прибор 1 свободен , то требование немедленно поступает на обслуживание . Если же прибор занят , то требование остается в накопителе , становясь в конец имеющейся очереди. Как только прибор 1 заканчивает производимую им операцию , немедленно принимается к обслуживанию требование из очереди т.е . из накопителя , и начинается новая операция обслуживания . Если требований в накопителе нет , то новая операция не начинается , стрелкой а показан поток требований от источника к накопителю , стрелкой b - поток обслуженны х требований. Система массового обслуживания с ожиданием 1. Постановка задачи. Мы изучим здесь классическую задачу теории массового обслуживания в тех условиях , в каких она была рассмотрена и решена Эрлангом . На m одинаковых приборов поступает простейший поток требований интенсивности . Если в момент поступления требования имеется хотя бы один свободный прибор , оно немедле нно начинает обслуживаться . Если же все приборы заняты , то вновь поступившее требование становится в очередь за всеми теми требованиями , которые поступили раньше и еще не начали обслуживаться . Освободившийся прибор немедленно приступает к обслуживания оче р едного требования , если только имеется очередь . Каждое требование обслуживается только одним прибором , и каждый прибор обслуживает в каждый момент не более одного требования . Длительность обслуживания представляет собой случайную величину с одним и тем же распределением вероятностей F(x). Предполагается , что при x 0 F(x) = 1 - e - x , (1) где > 0 - постоянная. Эрланг решил эту задачу , имея в виду постановки вопросов возникших к тому времени в телефонном деле. Выбор распределения (1) для описания деятельности обслуживания произведен не случайно . Дело в том , что в этом предположении задача допускает простое решение , которое с удовлетворительной для практики точности оп исывает ход интересующего нас процесса . Мы увидим , что распределение (1) играет в теории массового обслуживания исключительную роль , которая в значительной мере вызвана следующим свойством : При показательном распределении длительности обслуживания распреде ление деятельности оставшейся части работы по обслуживанию не зависит от того , сколько оно уже продолжалось. Действительно , пусть f a (t) означает вероятность того , что обслуживание , которое уже продолжается время a, продлится еще не менее чем t. В предполож ении , что длительность обслуживания распределена показательно , f 0 (t)=e - t . Далее ясно , что f 0 (a)= e - a и f 0 (a+t)= e - (a+1) . А так как всегда f 0 (a+t)= f 0 (a)f a (t), то e - (a+t) = e - a f 0 (t) и , следовательно, f a (t) = e - t = f o (t). Требуемое доказано. Несомненно , что в реальной обстановке показательное время обслуживания является , как правило , лишь грубым приближением к действительности . Так , нередко время обслуживания не может быть меньше чем , чем некоторая определенная величина . Предположение же (1) приводит к тому , что значительная доля требований нуждается лишь в кратковременной оп е рации близкой к 0. Позднее перед нами возникает задача освобождения от излишнего ограничения , накладываемого предположением (1). Необходимость этого была ясна уже самому Эрлангу , и он в ряде работ делал усилия найти иные удачные распределения для длительн о сти обслуживания . В частности , им было предложено так называемое распределение Эрланга , плотность распределения которого дается формулой где , > 0, а k - целое положительное число. Распределение Эрланга представляет собой распределение суммы k независимых слагаемых , каждое из которых имеет распределение (1). Обозначим для случая распределения (1) через время обслуживания требования . Тогда средняя длительность обслуживания равна Это равенство дает нам способ оценки параметра по опытным данным. Как легко вычислить , дисперсия длительности обслуживания равна 2. Составление уравнений. система с ожиданием в случае простейшего потока и показательного времени обслуживания представляют собой случайный процесс Маркова. Найдём те уравнения , которым удовлетворяют вероятности P k (t). Одно из уравнений очевидно , а именно для каждого t . (2) Найдем сначала вероятность того , что в момент t+h все приборы свободны . Это может произойти следующими способами : в момент t все приборы были свободны и за время h новых требований не поступало ; в момент t один прибор был занят обслуживанием требования , все остальные приборы свободны ; за время h обслуживание требования было завершено и новых требований не поступило. Остальные возможности , как-то : были заняты два или три прибора и за время h работа на них была закончена - и меют вероятность o(h), как легко в этом убедится. Вероятность первого из указанных событий равна вероятность второго события Таким образом, Отсюда очевидным образом приходим к уравнению (3) Перейдем теперь к составлению уравнений для P k (t) при k 1. Рассмотрим отдельно два различных случая : 1 k m и k m. Пусть вначале 1 k m. Перечислим только существенные состояния , из которых можно прийти в состояние E k в момент t+h. Эти состояния таковы : В момент t система находилась в состоянии E k , за время h новых требований не поступило и ни один прибор не окончил обслуживания . Вероятность этого события равна В момент t система находилась в состоян ии E k-1 , за время h поступило новое требование , но ни одно ранее находившееся требование не было закончено обслуживанием . Вероятность этого события равна В момент t си стема находилась в состоянии E k+1 , за время h новых требований не поступило , но одно требование было обслужено . Вероятность этого равна Все остальные мыслимые возмож ности перехода в состояние E k за промежуток времени h имеют вероятность , равную 0(h). Собрав воедино найденные вероятности , получаем следующее равенство : Несложные пре образования приводят нас к такому уравнению для 1 k m: (4) Подобные же рассуждения для k m приводят к уравнению `(5) Для определения вероятностей P k (t) мы получили бесконечную систему дифференциальных уравнений (2)-(5). Ее решение представляе т несомненные технические трудности. 3. Определение стационарного решения. В теории массового обслуживания обычно изучают лишь установившееся решение для t . Существо вание таких решений устанавливается так называемыми эргодическими теоремами , некоторые из них позднее будут нами установлены . В рассматриваемой задаче оказывается , что предельные или , как говорят обычно , стационарные вероятности существуют . Введем для них обозначения P k . Заметим дополнительно , (этого мы также сейчас не станем доказывать ), что при t . Сказанно е позволяет заключить , что уравнения (3), (4) и (5) для стационарных вероятностей принимают следующий вид : (6) при 1 k m (7) при k m (8) К этим уравнениям добавляется нормирующее условие (9) Для решения полученной бесконечной алгебраической системы введем обозначения : при 1 k m при k m Система уравнений (6)-(8) в этих обозначениях принимает такой вид : z 1 =0, z k -z k+1 =0 при k 1 Отсюда заключается , что при всех k 1 z k =0 т.е . при 1 k m k P k = P k-1(10) и при k m m P k = P k-1(11) Введем для удобства записи обозначение = / . Уравнение (10) позволяет заключить , что при 1 k m (12) При k m из уравнения (11) находим , что и следовательно , при k m (13) Остается найти P 0 . Для этого в (9) подставляем выра жения P k из (12) и (13). В результате Так бесконечная сумма , стоящая в квадратных скобках , находится только при условии , что m(14) то при этом положении находим равенство (15) Если условие (14) не выполнено , т.е . если m, то ряд , стоящий в квадратной скобке уравнения для определения P 0 , расходится и , значит , P 0 должно быть равно 0. Но при этом , как следует из (12) и (13), при всех k 1 оказывается P k =0. Методы теории це пей Маркова позволяют заключить , что при m с течением времени очередь стремится к по вероятности. 4. Некоторые подготовительные результаты. Во введении мы уже говорили , что для задачи с ожиданием основной характеристикой качества обслуживания является длительность ожидания требованием начала обслуживания . Длительность ожидания представляет собой случайную величину , которую обозначим бук вой . Рассмотрим сейчас только задачу определения распределения вероятностей длительности ожидания в уже установившемся процессе обслуживания . Обозначим далее через P t вероятность того , что длительность ожидания превзойдет t, и через P k t вероятность неравенства , указанного в скобке , при условии , что в момент поступления требования , в очереди уже находится k требований . В силу формулы полной вероятности имеем равенство P t = .(16) Прежде чем преобразовать эту формулу к виду , удобному для пользования , приготовим некоторые необхо димые нам для дальнейшего сведения . Прежде всего для случаев m=1 и m=2 найдем простые формулы для P 0 . несложные преобразования приводят к таким равенствам : при m=1 P 0 =1- ,(17) а при m=2 (18) Вычислим теперь вероятность того , что все приборы будут заняты в какой-то наудачу взятый момент . Очевидно , что эта вероятность равна (19) Эта формула для m=1 принимает особенно простой вид : = ,(20) при m=2 (21) Напомним , ч то в формуле (19) может принимать любое значение от 0 до m (включительно ). Так что в формуле (20) , а в (21) 2. 5. определение функции распределения длительности ожидания. Если в момент поступления требования в очереди уже находились k-m требований , то поскольку обслуживание происходит в порядке очередности , вновь поступившее требование должно ожидать , когда будут обслужены k-m+1 требований . Пусть q s (t) означает вероятность того , что за промежуток времени длительности t после поступления интересующего нас требования закончилось обслужива ние ровно требований . Ясно , что k m имеет место равенство Так как распределение длительности обслуживания предположено показательным и независящим ни от того , сколько требований находится в очереди , ни от того , как велики длительности обслуживания других требований , то вероятность за время t не завершить ни одного обслуживания (т.е . вероятность того , что не освободится ни один из приборо в ) равна Если все приборы заняты обслуживанием и еще имеется достаточная очередь требований , которые ожидают обслуживания , то поток обслуженных требований будет простей шим . Действительно , в этом случае все три условия - стационарность , отсутствие последействия и ординарность - выполнены . Вероятность освобождения за промежуток времени t ровно s приборов равна (это можно показать и простым подсчетом ) Итак , и , следовательно, Но вероятности P k известны : поэтому очевидными преобразованиями приводим правую часть последнего равенства к виду Из формул (13) и (19) следует , что , поэтому при t>0 (22) Само собой разумеется , что при t<0 . Функция имеет в точке 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<1. Вероятность того , что прибывший самолет не задерживается , равна (14.54) Вероятность того , что будет задержан один самолет , найдем , рассмотрев все задержки одиночных самолетов между двумя незадерживаемыми самолетами . Самолет , который будет задержан , должен прибыть через промежут ок времени t 1 2T-t 1 . Таким образом , искомая вероятность совместного поя вления этих двух событий равна Вероятность того , что будет задержано два самолета , находится аналогично (рассматривается два задерживаемых самолета между двумя незадерж иваемыми ) путем вычисления вероятности совместного появления событий : t 1 < T - для первого задерживаемого самолета , следующего за незадерживаемым ; t 2 < 2T- t 1 - для второго задерживаемого самолета , следующего за первым задерживаемым ; t < 3T- t 1 - t 2 - для незадерживаемого самолета , следующего непосредственно за двумя задерживаемыми. В результате для двух задерживаемых самолетов получаем .(14.55) Общее выражение для вероя тности того , что задерживается n-1 самолетов , имеет вид n T n-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 < (m+1)T: откуда после интегрирования по t ( t ) он определяет T как долю задерживаемых самолетов . Заметим , что при суммировании по m необходимо рассматривать интервалы (mT,(m+1)T). Отсюда находим также среднее время ожидания . Заметим , что время ожидания увеличивается с ростом T. Приведенное выше распределение дает критерии для определения необходимой пропускной способности аэропорта.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Жизнь делится на два этапа - сначала нет ума, потом здоровья.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Системы с ожиданием", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru