Задачи обслуживания в системах с потерями

Введение.

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

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

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

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

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

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

Раздел 1.

1. Входящий поток.

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

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

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

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

Процесс поступления  заявок на обслуживание есть случайный  процесс. Поток требований может быть описан некоторой функцией  , определяющей число требований, нуждающихся в обслуживании за промежуток времени . Функция есть случайная величина для каждого значения . Действительно, если мы выберем промежутки времени даже одинаковой продолжительности, то и в этом случае мы не можем быть уверены, что в каждый из этих промежутков времени поступит одинаковое число требований. Ведь за данный промежуток времени может и не поступить ни одного требования, а может поступить _{требований.}

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

Но функция  может принимать только целые положительные значения, поэтому она может быть задана более просто. Для полного определения потока требований достаточно знать, какова будет вероятность того, что за время поступит   требований, за время _{поступит} требований и т.д. Если эта вероятность будет известна для любой группы целых положительных _{и положительных} то поток требований будет полностью описан. Эту вероятность мы будем обозначать через  

Очевидно, что  эта вероятность может быть отлична  от нуля только в том случае, если при _{величины} удовлетворяют условию

Это утверждение  вытекает из того, что функция  не убывает с возрастанием . Значение функции 

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

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

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

1.2. Свойства потоков.

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

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

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

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

Нетрудно понять, что наличие свойства стационарности значительно облегчает изучение потока требований. Действительно, если известен характер потока требований, поступающих в обслуживающую  систему с некоторого начального момента , то для того чтобы получить характеристики потока начиная с момента , нет необходимости изучать поток заново. Можно воспользоваться характеристиками потока, полученными ранее. Число требований, поступающих в систему обслуживания после момента , т.е. _{, при наличии свойства стационарности будет подчиняться т}ому же закону, что и .

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

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

Обозначим , где Иными словами,

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

Стационарный  поток без последействия обладает одним важным свойством, заключающимся  в том, что его можно полностью  охарактеризовать системой функций _, где _{Для доказательства достаточно показать, что}  

можно выразить через _{, . Это и будет означать, что стационарный поток требований без последействия полностью характеризуется функциями}

Если за отрезки  времени  поступило соответственно требований, то это равносильно тому, что за время поступило требований, за время поступит _{требований и т.п. Поэтому вероятность того, что равна вероятности того, что} , где Для того, чтобы обеспечить общность записи принимаем _{. Следовательно,} 

Но промежутки времени  не пересекаются, поэтому события поступления _{требований за эти промежутки времени независимы.}

Применив теорему  умножения вероятностей, получим 

По условию  поток требований стационарный: 

Следовательно,  

Но  есть вероятность того, что за время поступит точно требований, а она равна _{Поэтому} 

где

Таким образом, указанное выше свойство действительно  имеет место, и для того, чтобы  описать стационарный поток без  последействия, достаточно получить систему  функций  _{где и Это свойство в значительной степени упрощает изучение таких потоков и облегчает  описание.}

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

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

Поток требований называется ординарным, если  

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

1.3.Простейший  поток.

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

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

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

Теорема 1. Для любого стационарного  потока существует предел 

где 

Величина  называется параметром потока. Она может быть неограниченно большой.

Функция является вероятностью того, что за время в систему поступит по крайней мере одно требование. Действительно, так как  

то  

Но_{, т.е.}  

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

Перейдем теперь к доказательству теоремы 1. Оно основано на следующей лемме.

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

Опираясь на лемму, для доказательства теоремы 1 достаточно показать, что функция удовлетворяет условиям леммы. Действительно, уже из определения следует, что . Если же выбрать промежуток достаточно большим, то вероятность появления в системе хотя бы одного требования за этот промежуток будет отлична от нуля, т.е. . Исключением может быть только случай, когда поток требований вообще отсутствует, что для нас не представляет никакого интереса. Из определения функции вытекает также, что она является возрастающей функцией. Теперь осталось показать справедливость равенства 

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

Но произведение неотрицательно, поэтому  

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

Теперь вернемся к простейшему потоку и исследуем  вид функций  при

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

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

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

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

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

_{которая равна} 

Оказывается, что  все слагаемые суммы, стоящей  в правой части этого равенства, кроме последних двух, являются бесконечно малыми величинами более высокого порядка, чем само приращение времени _{. Более того, оказывается, что их сумма есть бесконечно малая величина этого же порядка. Покажем это.}

Во-первых, очевидно, что 

Справедливость  этого вытекает из того, что  при

Во-вторых, очевидно, что если в сумме  _{продолжать суммирование неограниченно, то она не уменьшится, т.е.}  

Теперь покажем, что даже последняя сумма есть бесконечно малая величина по сравнению  с _{, т.е.}  

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

Если первые два слагаемых суммы, стоящей  в левой части этого равенства, перенести направо, то оно преобразуется  в следующее 

Сумма, стоящая  в этом новом равенстве справа, есть не что иное, как вероятность  поступления не менее двух требований за время _{. Сумма} есть вероятность непоступления ни одного требования или поступления точно одного требования за время _{. Следовательно,}

  _{есть вероятность  поступления двух, трех} или более требований за это время. Но выше мы эту вероятность обозначили _{и указали, что свойство ординарности,  которым обладает простейший поток, заключается в том, что =o(), т. е. есть бесконечно малая величина более высокого порядка, чем t.}

Поэтому  

при _.

Так как  _{, то тем более}

  при _{, что и требовалось доказать.}

Теперь преобразуем правую часть равенства (1). Сумма всех слагаемых, кроме последних двух, есть бесконечно малая более высокого порядка, чем _{, так как Поэтому} 

Найдем значения _{и . Из теоремы 1 следует, что вероятность} поступления по крайней мере одного требования за время отличается от на бесконечно малую величину более высокого порядка, чем , т. е. 

Но 

где —вероятность того, что ни одно требование не  поступит в систему за время , поэтому 

откуда 

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

Из этого равенства  можно определить значение искомой  величины _: 

Но мы уже  знаем, что 

Поэтому 

Полученные выражения (3) для  _{и (4) для подставим в (2). В результате получим уравнение, связывающее ,} и , 

Но так как  и то _{есть бесконечно малая более высокого порядка, чем , т. е.}  

Поэтому 

Перенеся  _{влево и разделив на} , получим 

Переходя к  пределу, получаем 

Предел _{равен нулю, т.к. — бесконечно малая более высокого порядка, чем .}

Таким образом, для определения   _{получена бесконечная рекуррентная система линейных однородных дифференциальных уравнений (5). Но так как выражено через ,то необходимо найти еще одно уравнение для определения . Это уравнение можно получить из условия} 

которое вытекает из свойства отсутствия последействия и теоремы умножения вероятностей. Последнее условие означает, что вероятность отсутствия требований за время равна произведению вероятности отсутствия требований за время (0, t) на вероятность отсутствия требований за время . Подставляя в это уравнение вмеcто _{выражение (3), получаем} 

Откуда 

Поделив правую и левую части этого уравнения на _{и перейдя к пределу при , получим} 

то есть 

Это — дифференциальное уравнение с раздёляющимися переменными.  
 

Отсюда получаем, что 

Для определения  произвольной постоянной С воспользуемся равенством (3), из которого следует, что 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Вместо функций   ₍k = 1,2,...) будем искать функции ( Если мы их найдем, то легко будет найти функции _{Для функций} получим следующую систему уравнений: 
 
 

, но  
 
 

При t = 0 получаем 

Отсюда 

Но величины_{, следовательно, их сумма может быть равна нулю только в случае, когда каждая из них равна нулю, т. е. (0) = 0 (}k = 2, 3,...) и _{(0) = 0. Эти условия имеют простой физический смысл. Они означают, что вероятность появления} k требований (k=1, 2,...) зa промежуток времени, не превышающий нуля, равна нулю.

  Итак, для  определения произвольных постоянных имеем следующие условия: 

Из (7) и (8) следует, что и₀ (t) = 1. Подставив и₀ (t) в первое уравнение (9), получим 

и после интегрирования 

Но  = 0 = С₁, поэтому u_l(t) =. Подставив во второе уравнение (9), получим 

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

Но при t=0  (0) = 0 = С₂, поэтому 

Аналогично получаем  

По индукции получаем, что 

Возвращаясь к_{, из (8) получаем} 

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

Простейший поток  полностью определяется системой функции (10). Функции _{если не считать} , зависят только от параметра потока λ.

  _{есть вероятность  поступления точно} k требований за время (0, t). Следовательно, для того чтобы дать полную характеристику простейшего потока, достаточно знать только одну величину — параметр потока.

Рассмотрим физический смысл λ. Легко показать, что для  простейшего потока параметр λ равен математическому ожиданию  числа требований, поступивших в систему за единицу времени. Чтобы доказать это, вычислим математическое ожидание числа требований, поступивших за промежуток времени (0, t). Оно равно 

Но сумма 

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

Следовательно, математическое ожидание числа требований за единицу времени, которое получается из выражения для при t=1, равно 

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

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

1.4. Время обслуживания.

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

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

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