1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987).djvu), страница 15
Описание файла
DJVU-файл из архива "1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987).djvu", который расположен в категории "". Всё это находится в предмете "теория массового обслуживания (асвк)" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 15 - страница
Покажем,что при этом предположении мы оказываемся в условиях процессов гибели и размножения. Действительно, поскольку распределение 0(х) обладает свойством «отсутствия памятна, анание того, что система в момент г находится в состоянии Е„определяет полностью вероятность системе находиться в состоянии Е1 в момент 1+Ь. Эта вероятность не изменяется от того, что нам становится известно, "ак долго ожидали требования, находящиеся в системе до момыта 1. Подсчитаем величины А„н д, для рассматриваемой задачи.
Поскольку на приборы поступает входящий простейший по- ТОК )т Х, ЕСЛИ МЫ НаХОдИМСя В СОСтсяинн Е„, И О<й(7Е, тО в состояние Ее-1 можно перейти за время Ь только одним способом — на одном из приборов будет завершено обслуживание за зтот срок. Таким образом, при О ~ е -" т имеем равенство ке йр. вски к= О, то ясно, что де = О. При й~ 7я переход иа состояния 76 ГЛ. 1. ЗАДАЧИ ТЕОРИИ .'ИАССОВОГО ОВСЛУЖИВАНИЯ Кь в состояние Еь, за время й может произойти двумя путями: за этот срок на одном из лг обслуживающих приборов обслуживание требования было аавершено; срок ожиданияодного из й — т ожидающих требований истек. Таким образом, р„тр+ +(й — т)У.
Из формул (12) 3 1.3 находим, что при й» т РА=йТ(„) Ры при й)т ..-Рф--~ П ю--)"-и) З=т+1 и, наконец, Р, ~~~~~ ( ) -(- ~ А Ц ((1 т) У+ тР). Р Р З1!ь +1 Я=п~+1 Система Аг!Л1!гя с временем ожидания, ограниченным произвольно распределенной величиной, исследована О. М. Юркевичем (11; см. также И. Н.
Коваленко, О. М. Юркевич Щ. й 1,8. Система с ограниченным временем пребывании 1. Постановка задачи, предположения. Каждое требование, поступающее в систему обслуживания, может находиться в системе не более чем время т. Таким образом, могут представиться три следующие несовместимые возмо1кностй: время ожидания и период обслуживания требования меньше, чем т (требование было полностью обслужено); время ожидания оказалось меньше, чем т, но оставшегося до т времени не хватило, чтобы полностью завершить обслуживание. В результате требование было потеряно, не будучи полностью обслуженным.
Наконец, мыслима третья возможность, когда время ожидания оказалось большим, чем т, и произошла чистая потеря без затраты времени на его обслуживание. С описанной системой обслуживания приходится иметь дело достаточно часто, мы ограничимся здесь рассмотрением следующего чисто качественного примера. Имеется вона действия некоторого прибора (счетчика частиц, радиолокатора и пр.). Каждое требование, приходящее через зту зону, может быть обслужено прибором, если только прибор не занят. Время нахождения требования в зоне равно т. За пределами зоны прибор уже лишен возможности обслуживать требования.
В каждый момент прибор может обслуживать только одно требование. Прибор от обслуживания одного требования без затраты времени переходит к обслуживанию другого. Каждое требование обслуживается только одним прибором. Ф сз. спстемА с огРАниченным ЕРеменем НРевыВАния 77 Если требования обслуживаются в порядке очередности их поступления, то чистых потерь не может быть. Действительно, мы предполагаем поток ординарным, и поэтому любые два требования поступают з систему раздельно, Пусть какие-нибудь два нз них постУпили соответственно в моменты 8о 8„Г, ( Гь Если Г, — 8~) т, то второе требование поступает в систему тогда, когда предыдущее ее уже покинуло.
Если же 8, — 8, ~ т, то первое из требований покидает систему самое позднее в момент ~,+ т, поэтому второе требование обслуживается по меньшей мере с момента 8, + т (оно обязано покинуть систему в момент 88+ т). Разумеется, все три случая, о которых мы говорили, возможны, если обслуяснванне происходит не в порядке очередности, а в порядке случайного выбора нз среды оясидающих. Рассмотрим случай упорядоченного обслуживания простейшего потока т одинаковыми приборами. Распределение длительности обслуживания — показательное с параметром 1А. Мы рассмотрим два случая: т = сопзг и т — случайная величина с распределенном 6(л) = ( — е '".
2. Случайный процесс, описывающий обслуживание. Как и в $ 1.7, мы сталкиваемся с необходимостью рассмотреть более сложный случайный процесс, чем процесс гибели и размножения для случая т=сопз$, поскольку знания того, сколько требований находится в системе в данный момент, совершенно недостаточно для заключения о том состоянии, в каком она будет находиться в последующие моменты времени. Судьба каждого требования в значительной мере определяется моментом его поступления. Обозначим через $~(~) случайную функцию, определенную посредством следующего условия: $;(8) = О, если в момент 8 8-й прибор свободен, в остальных случаях э;(1) равно времени, которое должно пройти с момента ~ до того момента, когда прибор с номером 8 освободится от обслуживания требований, поступивших до момента й Из постановки задачи, которая была нами описана, вытекает, что при любых г выполнено неравенство $~(г) ~ т.
Составим представление о геометрической структуре процесса ~~(8). С атой целью отложим по оси абсцисс время 1, а по оси ординат Оу — функцию $,(Г). Отметим моменты 81,, в которые поступают требования на 1-й прибор. Пусть до момента ~1, прибор был свободен. Это означает, что до этого момента ь,(г) = О, а в момент 81 функция $~(Г) испытала скачок. Если необходимая длительность обслуживания Ч;, равна или меньше т, то $1(81, + О)= Ч1,, а еслиц1 )т, то $1(11 + О) = т. При возрастании времени функции $~(1) убывает на, величину протекшего периода до тех нор, пока она не обратится в О или жо до ближайшего момента появления у прибора нового требования.
Рис, 2 дает представление о течении процесса э (8). 78 Гл. с ЗАдАчп теОРии ИАссового ОвслуживАния Введем теперь в рассмотрение т-мерный случайный процесс е(г)-(з (г), ", 4 (г)). Из определения ясно, что если в момент г в систему поступило требование, то время ожидания начала обслуживания для него равно ь (г) = инп $;(г).
Таким образом, процесс $(г) дает нам необходимые сведения о г,, г', Рис. 2 том, что ожидает поступившее в систему требование. Если имеется несколько приборов, для которых $~(г — О) достигают минимума, то требование выбирает любой из них наудачу. Процессы $(г), определенные нами в 2 1.7 и здесь, словесно описаны абсолютно одинаково. Однако особенности постановок задач существенно на них отразились, как зто наглядно видно из сравнения рис.
1 и 2: на одном из них функция $~(г) может принимать любые неотрйцательные значения, тогда как на другом она ограничена сверху величиной т. 3. Стационарное распределение. Уравнения для стационарного распределения случайного процесса Ь(г) приводить не будем, так как они вполне аналогичны соответствующим уравнениям для случаи ограниченного времени ожидания; это касается и способа их вывода.
Стационарные характеристики процесса Рх(хо ..., И,)„ аналогичные введенным в $ 1.7, имеют следующий вид: г -зх1 Рд(х„...,хь) = Рз — Ц~1 — е '), 0~(й<т — 1; Рв (яы ° > аз хт) = (' -»(~,-~-...+с,з)+Ьзезри...л,х) о<В(х; г.е;~т (в обоих случаях 0 < х, < т). коммеитхгии 79 Из формул для рааличных стационарных характеристик обслуживания, которые выводятся на основании приведенных вы- ~ соотношений, отметим формулу для функции ) (х), где 1(х) ~]х при х) О есть вероятность того, что поступившему требованию придется ожидать начала обслуживания от х до х+ох единиц времени: Решение методом интегро-дифференциальных уравнений найдено И. Н.
Коваленко (1]. См. также Баррер [1), (2]. 4. Длительность пребывания в системе ограничена случайной величиной..Во введении было сказано, что в ряде задач практического характера естественно считать т не постоянной величиной, как мы это делалн до сих пор, а случайной. В предположении 6(х) =- Р(т (х) = 1 — е-'" задача сводится к рассмотрению схемы гибели и размножения, для которой Ха= Х при [с~О, р» = [с()а+т) при 1 ( )) ~ т и, наконец, )ьл = т)л+)сч при й ~ т. Формулы (12) — (13) иэ 2 1,3 приводят к равенствам: при [г < пз при )с~тп л ре л ~ рл=[ (р + т)м Ц (зт + з~р) Комментарии Практяческие аадачп, связанпые с марковсквми моделями систем массового обслуживаяиа, связаны с решением систем линейных уравнений большой раамерности. Нашли примеяеяие как общие вычислительные методы, так и методы, специально разработаияые для анализа систем обслужизаккя.
См. д. К. Фаддеев и В. Н. Фаддеева [1], М. А. Шпепс [1], Г. П. Нашарив и А. И. Громов [1], Шветлик [Ц. Дополнительная литература по системам с ограяичевиями: Коэн [Ц, О М. Юркеввч [1], В. В. Морозов [1], Н. Д. Шваб [1], И. Н. Ковалеико, О М. Юркевич [1), [2]. Для марковских моделей систем обслуживания решались многие задачи оптимиаации, свяааипые со стратегиями управлепия потоком требовавий, выбором иятеясивяостя обслуживания з зависимости от величины очереди, выбором оптимальяого правила приоритетною обслуживакия, Математическая основа — теория оптимального управления марковским процессоль См.
рыков [1], [2], [3]. Припцилы решения подобных аадач методом линейного програмазировакия раскрыты в работе В. В. Мовы и Л. А. Повомарекко [1]. ГЛАВА 2 113УЧЕНИЕ ВХОДЯЩЕГО ПОТОКА ТРЕБОВАНИЙ з 21. Несколько примеров 1. О понятии входящего потока. Первичным понятием теории массового обслуживания, которому в последнее время уделяется большое внимание, является понятие потока требований, поступающих в систему обслуживания. В гл. 1 мы познакомились с простейшим потоком, который в теории массового обслуживания до последнего времени играет центральную роль. С позиций специалиста в области теории вероятностей простейший поток представляет собой очень важный, во частный случай так называемых дискретных случайных процессов. В последнее время выяснилось, что и в приложениях кростейшнй поток является не единственным, с которым приходится иметь дело.