Пусть поток заявок детерминированный (события наступают в определенные моменты времени). Тогда { tj } – заданы либо таблицей, либо tj = f (j) или tj = f (tj -1, …, tj - k). В системах массового обслуживания рассматриваются случайные потоки заявок, то есть моменты наступления заявок 
являются случайными. Вместо случайных { tj } рассматривают случайную длину интервала x между двумя последовательными заявками x j = tj +1- tj, (j ³1). Пусть интервал наблюдения системы имеет следующий вид: [ 0, T ]. Тогда, предполагая, t1 =x 1 получим
,
x - случайная величина.
2. Классификация систем массового обслуживания. Простейший поток требований. Время обслуживания. Расчетные формулы ТМО.
Каждая СМО предназначена для обслуживания (выполнения)некоторого потока заявок (требований), поступающих на вход системы большей частью не регулярно, а в случайные моменты времени. Потоком событий (в данном случае заявок) называют последовательность событий, наступающих одно за другим в какие-то заранее неизвестные, случайные моменты времени.
3. Формальное представление процессов функционирования
систем массового обслуживания. Пусть СМО состоит из n линий, способных одновременно обслуживать заявки. Линия в любой момент времени находится в одном из двух состояний: свободна, занята. Пусть в момент t в СМО поступает заявка. Если есть свободные линии, то заявка обслуживается, иначе заявка ставится в очередь в системе. Пусть t n - предельное время пребывания в очереди. Если за время t n заявка не принята к обслуживанию, то она потеряна.
В зависимости от величины t n СМО делятся на три класса.
Первый класс: t n = 0, то есть заявка либо сразу принимается, либо сразу получает отказ и теряется. Такая СМО – система с отказами. Показатели системы с отказами: вероятность отказа, среднее число отказов за данный интервал времени.
Второй класс: нет отказов. Такая СМО – система с ожиданием. Показатели системы с ожиданием: среднее время ожидания, средняя длина очереди.
Третий класс: 0< <¥. СМО с ожиданием в течении t n и с отказом, при ожидании t > t n. Это СМО с ограниченным ожиданием. Показатели СМО с ограниченным ожиданием: среднее время ожидания, среднее число отказов, средняя длина очереди, вероятность отказа.
СМО характеризуется так же параметром t з – время обслуживания заявки или время занятости линии. Обычно параметры t з и t n считаются случайными величинами с заданными законами (или совместным законом) распределения. Иногда один из них, или оба фиксированы.
Порядок занятия линий заявками.
Если есть очередь заявок, то освобождающиеся линии занимаются немедленно в порядке их освобождения. Если очереди заявок нет и имеются свободные линии, то появившаяся заявка занимает одну из свободных линий согласно специальным правилам.
Правила (часто использующиеся на практике):
1. Линии занимаются в порядке их номеров. Линия с большим номером не используется, если свободна линия с меньшим номером.
2. Линии занимаются в порядке очереди. Освободившаяся линия не используется, если есть ранее освободившаяся линия.
3. Линии занимаются в случайном порядке в соответствии с заданными вероятностями. Если имеется n св свободных линий, то заданы вероятности 
занять линию. В простейшем случае 
.
В общем случае pi (вероятность занять i -ю свободную линию) зависит от номеров линий, моментов их освобождения и других параметров.
Альтернативные правила обслуживания заявок, при наличии очереди заявок:
1. Заявки обслуживаются в порядке поступления, то есть освободившаяся линия обслуживает ту заявку, которая раньше других поступила в систему.
2. Заявки принимаются к обслуживанию в случайном порядке в соответствии с заданными вероятностями. Если в момент освобождения линии в очереди m заявок, то вероятность q обслуживания конкретной заявки принимается равной 
. В общем случае qi зависит от времени пребывания заявки в системе, времени до отказа и других параметров.
Реальный процесс массового обслуживания состоит из последовательности фаз обслуживания, выполняемой различными устройствами. При этом следующее устройство приступает к обслуживанию заявки тогда, когда работа предыдущего с данной заявкой завершена.
Пример 1. Многофазное обслуживание покупателей.
1. Выбор товара и оформление товарного чека
2. Оплата в кассе.
3. Получение товара.
Пример 2. Технологический процесс.
Изделие может поступить на обработку станком (n +1)-1 фазы лишь тогда, когда его обработка на станке n -й фазы закончена.
Обслуживание с приоритетом.
Каждой заявке, поступающей в систему, приписывается некоторый коэффициент преимущества (приоритет). Тогда возникают следующие правила обслуживания.
1. В момент освобождения канала на обслуживание поступает заявка из очереди с наибольшим приоритетом.
2. Прекращается обслуживание заявки, если в систему поступает заявка с большим приоритетом.
Пример (СМО с приоритетом). Доставка телеграмм (сначала молнии, потом срочные, потом обычные).
4.Характеристики системы массового обслуживания. Величины, которые необходимо определить:
3. Для системы с отказами, это средняя доля R (t 0, t) отказов за интервал (t 0, t 0+ t).
R (t 0, t) определяется следующим образом. Рассмотрим совокупность n независимых реализаций процесса на интервале (t 0, t 0+ t). Пусть случайно, путем генерирования равновероятных событий, выбрана i -я реализация. Пусть количество заявок поступивших для обслуживания в этой реализации случайная величина равная Ni (t 0, t). Пусть 
- среднее количество заявок поступающих за интервал (t 0, t 0+ t). Количество заявок mi (t 0, t) получивших отказ – случайная величина. Пусть 
- среднее количество отказов. Тогда
Иногда в качестве характеристики системы с отказами используется p (t 0, t) – вероятность того, что на интервале (t 0, t 0+ t) не будет отказов.
4. Для систем с ожиданием показателями качества обслуживания могут быть среднее значение времени ожидания или среднее значение длины очереди.
5. Для смешанных систем с отказами и ожиданием характеристиками являются все вышеуказанные показатели.
Теоретически результаты в СМО получены для простейших систем обработки (однородных и пр.) и потоков заявок.
Имитационное моделирование рассматривает реальные задачи массового обслуживания (многофазные системы и неоднородные потоки заявок) на основе случайных реализаций заданных потоков однородных заявок и моделирования процесса обработки заявок. При этом оцениваются не только асимптотические характеристики системы, но и ее характеристики в переходном режиме.
5. Формирование реализаций случайных потоков однородных событий. Рассмотрим некоторые основные теоретические понятия.
Случайный поток однородных событий называется потоком с ограниченным последствием, если случайные величины x i – независимы.
В этом случае совместная функция плотности
f (z 1, z 2, …, zk) = f 1(z 1) f 2(z 2) … fk (zk),
где fj (zj) – функция плотности случайной величины x j.
Поток однородных событий стационарный, если вероятность pk (t 0, t) появления k событий за промежуток времени (t 0, t 0+ t) не зависит от t 0, а зависит только от t и k.
Случайный поток с ограниченным последствием называется стационарным, если выполнено следующее:
f 2(z) = f 3(z) = … = fk (z) = f (z),
т. е. стационарный поток с ограниченным последствием зависит только от распределения f 1(z 1) и распределения f (z).
Среднее значение x j, j ³2 вычисляется по формуле
,
где m - средняя длина интервала времени между последовательными заявками. Тогда 
- среднее количество заявок в единицу времени. l - плотность (интенсивность) потока.
Например. Для f (z)=1/ b, 0£ z £ b – равномерное распределение на [0, b ],
.
Для стационарных потоков с ограниченным последствием справедлива формула Пальма
.
Отсюда для потока с равномерным распределением интервалов получаем
.
Тогда
.
Равномерный поток часто используется на практике.
Поток событий называется ординарным, если для вероятности p (t 0, t) появления двух и более событий за промежуток времени (t 0, t 0+ t) при любом t 0 выполнено условие
.
Иногда в приложениях рассматриваются групповые заявки, образующие сгусток событий, то есть неординарный поток событий. Для описания неординарных потоков необходимо, кроме распределения { tj } задать распределение количества заявок, поступающих в момент { tj }.
Случайный поток однородных событий без последствия. Если вероятность pk (t 0, t) наступления k событий за промежуток времени (t 0, t 0 + t) не зависит от того, что происходило до момента времени t 0. Этот поток является частным случаем потока с ограниченным последствием.
Простейший поток однородных событий – стационарный, ординарный и без последствия.
Для простейшего потока вероятность pk (t) наступления k событий за интервал времени длины t выражается законом распределения Пуассона
.
Простейший поток называют пуассоновским.
Для простейшего потока функция плотности f (z) случайных величин x j, j > 0 имеет следующий вид
,
где l - интенсивность (плотность) потока.
Формула Пальма показывает, что в этом случае
.
Поток Эрланга порядка m – ординарный стационарный поток с ограниченным последствием, для которого
.
Плотность этого потока 
.
Интервалы x j при j > 1 потока Эрланга порядка m представляются в виде суммы m независимых случайных величин, имеющих показательное распределение с параметром l*.
6. Обслуживание заявок, в общем случае, также длится не постоянное, заранее известное время, а случайное время, которое зависит от многих случайных, порой неизвестных нам, причин. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться не обслуженные заявки, что приводит к перегрузке СМО, в некоторые же другие интервалы времени при свободных каналах на входе СМО заявок не будет, что приводит к недогрузке СМО, т.е. к простаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо "становятся" в очередь, либо по какой-то причине невозможности дальнейшего пребывания в очереди покидают СМО не обслуженными. Схема СМО изображена на рисунке 6.1.
Таким образом, во всякой СМО можно выделить следующие основные элементы: входящий поток заявок; очередь; каналы обслуживания; выходящий поток обслуженных заявок.
Рисунок 6.1 – Схема системы массового обслуживания
Каждая СМО в зависимости от своих параметров: характера потока заявок, числа каналов обслуживания и их производительности, а также от правил организации работы обладает определенной эффективностью функционирования (пропускной способностью), позволяющей ей более или менее успешно справляться с потоком заявок.
7. Предметом изучения теории массового обслуживания является СМО. Цель теории массового обслуживания — выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности функционирования СМО.
Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее организации (параметров): характера потока заявок, числа каналов и их производительности и правил работы СМО).
Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс. Случайным процессом (или случайной функцией) называется соответствие, при котором каждому значению аргумента (в данном случае — моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае - состояние СМО). Случайной величиной называется величина, которая в результате опыта может принять одно, но неизвестное заранее, какое именно, числовое значение из данного числового множества.
Поэтому для решения задач теории массового обслуживания необходимо этот случайный процесс изучить, т.е. построить и проанализировать его математическую модель.
8. Классификация СМО. В СМО потоками событий являются потоки заявок, потоки "обслуживании" заявок и т. д. СМО по наличию того или иного признака можно разделить следующим образом:
1. По характеру поступления требований (заявок) можно разделить на системы с регулярным и случайным потоками поступления требований в систему. Случайный поток требований подразделяется на стационарный и нестационарный.
Поток событий называется стационарным, если вероятность наступления того или иного числа событий за какой-либо промежуток времени зависит только от длины этого промежутка и не зависит от момента его начала, в противном случае – нестационарный. Например, если число автомашин, приходящих на склад, не зависит от времени суток, то поток требований – стационарный.
2. По количеству поступающих требований в один момент времени делятся на системы с ординарным и неординарным потоками требований. Если вероятность поступления двух или более требований в один момент равна нулю или имеет столь малую величину, что ею можно пренебречь, то имеем систему с ординарным потоком требований. Например, поток требований – автосамосвалы, обслуживающие экскаватор, - можно считать ординарным, так как вероятность поступления двух и более самосвалов под погрузку к экскаватору – каналу обслуживания – очень мала и ею можно пренебречь.
3. По связи между требованиями делятся на системы без последействия от поступивших требований и с последействиями. Если вероятность поступления требований в систему в некоторый момент не зависит от того, сколько уже требований поступило в систему, т.е. не зависит от предыстории изучаемого процесса, то мы имеем задачу без последействия, в противном случае – с последействием. Примером задачи без последействия может служить оптовая база по продаже некоторых продуктов (канал обслуживания), на которую приходят покупатели (требования), причем число обслуживаемых покупателей предполагается неограниченным.
4. По характеру поведения требования делятся на систему с отказами, с ограниченным ожиданием и с ожиданием без ограничения.
- если вновь поступившее требование на обслуживание застает все каналы обслуживания уже занятыми и оно покидает систему, то имеем систему с отказами. Требование может покинуть систему и в том случае, когда очередь достигла определенных размеров. Если, например, на станции технического обслуживания скопилось много автомашин, то целесообразнее покинуть систему. Если при посадке самолета полоса приземления занята, он покидает аэродром;
- если поступившее требование застает все каналы обслуживания занятыми и становится в очередь, но находится в ней ограниченное время, после чего, не дождавшись обслуживания, покидает систему, то имеем систему с ограниченным ожиданием. Примером такого «нетерпеливого требования» может быть автосамосвал с раствором. Если время ожидания велико, то во избежание затвердения раствора он может быть разгружен на другой стройке;
- если поступившее требование, застав все каналы обслуживания занятыми, вынуждено ожидать своей очереди до тех пор, пока оно не будет обслужено, то имеем систему с ожиданием без ограничения. Пример: самолет, который находится на аэродроме до тех пор, пока не освободится взлетная полоса.
5. По способу выбора требований системы делятся на обслуживание с приоритетом, по мере поступления, случайно, последний обслуживается первым. Иногда, в этом случае говорят о дисциплине обслуживания:
- если система массового обслуживания охватывает несколько категорий требований и по каким-либо соображениям необходимо соблюдать различный подход к их отбору, то имеем систему с приоритетом. Так, при поступлении изделий на стройплощадку в первую очередь монтируются те, которые необходимы в данный момент;
- если освободившийся канал обслуживает требование, ранее других поступившее в систему, то имеем систему с обслуживанием требований по мере их поступления. Это наиболее распространенный класс систем. Например, покупатель, подошедший первым к продавцу, обслуживается первым. Этот способ выбора требований на обслуживание применяется там, где в силу технических, технологических или организационных условий требования не могут опережать друг друга;
- если требования из очереди в канал обслуживания поступают в случайном порядке, то имеем систему со случайным выбором требований на обслуживание. Пример: выбор слесарем-сантехником одной из нескольких заявок, поступивших от жильцов на устранение некоторых неисправностей (при условии, что заявки на одну и ту же неисправность). Выбор здесь, как правило, определяется местоположением самого рабочего: он выбирает заявку, наиболее близко расположенную к нему, если никакие другие факторы не предопределяют иной выбор;
- последний обслуживается первым. Этот способ выбора требований на обслуживание используется в тех случаях, когда удобнее или экономнее брать на обслуживание требование, позже всех поступившее в систему. Так, при укладке строительных изделий в штабель удобнее брать из штабеля (очереди) изделие, поступившее последним.
6. По характеру обслуживания требований системы делятся на системы с детерминированным и случайным временем обслуживания.
Если интервал времени между моментом поступления требования в канал обслуживания и моментом выхода требования из этого канала постоянно, то имеем систему с детерминированным временем обслуживания, в противном случае – со случайным.
7. По числу каналов обслуживания делятся на одноканальные и многоканальные системы. Так, при монтаже дома может быть использован только один подъемный кран (один канал обслуживания) или несколько (много каналов) для обслуживания прибывающих на стройку изделий.
8. По количеству этапов обслуживания делятся на однофазные и многофазные системы. Если каналы обслуживания расположены последовательно и они неоднородны, так как выполняют различные операции обслуживания, то имеем многофазную систему массового обслуживания. Примером двухфазной СМО может быть, например, обслуживание автомобилей на станции ТО (мойка, диагностирование и т.д.).
9. По однородности требований системы делятся на однородные и неоднородные потоки требований. Так, если под погрузку прибывают автомобили одной грузоподъемности, то такие требования наз. однородными, если разной грузоподъемности – неоднородными.
10. По ограниченности потока требований делятся на замкнутые и разомкнутые системы. Если поток требований ограничен и требования, покинувшие систему, могут в нее возвращаться, то имеем замкнутую систему, в противном случае – разомкнутую. Примером замкнутой системы может служить система ЭВМ – пользователь, в которой пользователь, как правило, прикрепляется к ЭВМ и обслуживается ею в течение определенного времени.
Классическим примером замкнутой СМО служит работа группы наладчиков в цеху. Станки являются источниками заявок на обслуживание, и их количество ограничено, наладчики — каналы обслуживания. После проведения ремонтных работ вышедший из строя станок снова становится источником заявок на обслуживание.
3. Сетевые модели. Сетевой график. События и работа. Критический путь. До появления сетевых методов планирование работ, проектов осуществлялось в небольшом объеме. Наиболее известным средством такого планирования был ленточный график Ганта, недостаток которого состоит в том, что он не позволяет установить зависимость между различными операциями.
Рассмотренные до сих пор методы оптимизации не позволяют решать такие важные для практической деятельности задачи, как планирование научно-исследовательских и опытно-конструкторских работ, проектирование машин, технологий и предприятий, опытное производство и испытание систем (машин) и т. д., в которых участвуют организации и предприятия различных ведомств, различные подразделения одного предприятия и т. п. Сетевые методы планирования позволяют находить оптимальные решения и этих сложных по своей структуре задач. Сетевое планирование служит для составления рационального плана решения производственной задачи в кратчайший срок и с минимальными затратами. Методы сетевого планирования дают возможность своевременно оценивать "узкие" места, вносить необходимые коррективы в организацию решения.
Основу данных методов составляют сетевые модели. Под сетевой моделью понимают модель комплекса взаимосвязанных работ, заданную в форме сети, отображающей упорядоченность работ по времени. Данная модель включает также и другие характеристики системы — время, стоимость, ресурсы, относящиеся к отдельным элементам или ко всей системе в целом. Еще одно определение: сетевая модель – графическое изображение плана выполнения комплекса работ, состоящего из нитей (работ) и узлов (событий), которые отражают логическую взаимосвязь всех операций. В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа. Граф – схема, состоящая из заданных точек (вершин), соединенных системой линий. Отрезки, соединяющие вершины, называются ребрами (дугами) графа.
Различают два основных вида представления сетевых моделей: сетевые графики и табличные (цифровые) представления сетевой модели. Сетевые графики (это ориентированный граф без контура) используются для анализа сетевых моделей человеком. Табличное представление используется для анализа моделей на ЭВМ. Сетевой график содержит два основных элемента (рис.): работу и событие.
Работа – это активный процесс, требующий затрат ресурсов, либо пассивный (ожидание), приводящий к достижению намеченного результата. На графике работы обозначаются безмасштабными стрелками. Цифры на стрелках обозначают оценки, например, времени выполнения работ. Событие не является процессом и не имеет продолжительности, а есть результат окончания одной или нескольких работ. На графике события обозначаются кружками, цифры в кружках — номера событий. Событие, не имеющее входящих работ, называют исходным, а не имеющее выходящих работ, — завершающим. Завершающее событие называют целевым, определяющим достижение цели всего комплекса работ. Для установления зависимости не связанных работой событий между ними вводится фиктивная работа. Фиктивная работа имеет нулевые затраты времени для ее выполнения. Она наносится на график пунктирной линией и вводится в график лишь для того, чтобы изобразить на сети требуемую очередность работ. При этом возможны совершенно различные сочетания работ и событий: данная работа должна быть завершена до начала следующей (последовательная цепочка событий); работы могут выполняться одновременно (из одного кружка выходит несколько стрелок); прибытие новых материалов, оборудования и т. д. обусловливает возможность начала новой работы (0 — события). Сетевые модели могут быть как вероятностными (показатели работы в этих моделях заданы в виде случайных величин), так и детерминированными (величина задана в виде константы). Сетевой график представляет собой общую картину проекта, в нем учитываются все требования, связанные с выполнением работ. Сетевой график может включать или все мельчайшие детали проекта, или только общие контуры основных видов работ. Независимо от целей, для которых используются сетевые графики, принципы их построения и анализа остаются неизменными. Построение сетевых графиков.
Для построения сетевых графиков необходимо выполнить следующие работы: составить перечень работ (детализировать все работы, виды деятельности, задачи и т. п., необходимые для доведения проекта до практического результата); составить перечень ограничений (определить, например, последовательность выполнения работ исходя из технологических и организационных факторов); оценить время (стоимость) выполнения каждой из работ.
Фиктивная работа – это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.
Событие – это результат (промежуточный или конечный) выполнения одной или нескольких предшествующих работ.
Путь – это любая непрерывная последовательность (цепь) работ и событий. Путь, начинающийся с исходного события и кончающийся завершающим, называется полным.
Критический путь – это путь, не имеющий резервов и включающий самые напряженные работы комплекса. Работы, расположенные на критическом пути, наз. критическими. Все остальные работы являются некритическими (ненапряженными) и обладают резервами времени, которые позволяют передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ.
Работа представляет собой выполнение некоторого мероприятия, например определенной технологической, транспортной или складской операции. Работа связана с затратой времени и расходом ресурсов, она должна иметь начало и конец. На графике работа обозначается стрелкой, над которой указывают ее номер (прописная буква с индексом), а под ней - продолжительность (в скобках).
Событиями называются начальные и конечные точки работы, например, начало или окончание производственной операции. Событие не является процессом и поэтому не сопровождается затратами времени или ресурсов. На графике событие (рисунок 6.2) обозначается кружком с буквенным обозначением внутри (строчная буква с индексом).
Относительно данной работы события могут быть предшествующими (непосредственно перед ней) и последующими (непосредственно за ней). Относительно данной работы другие работы могут быть предшествующими и последующими. Каждая входящая в данное событие работа является предшествующей каждой выходящей работе, каждая выходящая работа — последующей для каждой входящей.