Введение

(к оглавлению)

 

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

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

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

Содержание заданий на выполнение работ лабораторного практикума предполагает знакомство с основными понятиями теории вероятностей и математической статистики, а также наличие базовых навыков работы с электронными таблицами (приложение Excel пакета Microsoft Office). Для выполнения некоторых дополнительных заданий может потребоваться знание основных конструкций языка С++.

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

1.     Показатели СМО

 

Цель работы:

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

-    Освоение приемов практического оценивания параметров исследуемых систем.

 

Теоретические сведения

 

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

Для задания и описания эффективности функционирования конкретной СМО используются такие показатели как:

- среднее число заявок, находящихся в СМО;

- среднее число заявок, находящихся на обслуживании;

- среднее число заявок, находящихся в очереди;

- среднее время ожидания в очереди;

-    среднее время нахождения в СМО.

 

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

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

-   закон распределения времени ожидания;

-   средний доход, приносимый СМО в единицу времени, и т.д.;

-   среднее время простоя системы;

-   закон распределения длительности ожидания требования в очереди

и другие.

 

Выбор показателей зависит от вида системы.

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

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

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

-    среднее время ожидания заявки в очереди,

-    среднее число заявок в очереди,

-    среднее число заявок в системе,

-    среднее время пребывания заявки в системе,

-    коэффициент простоя,

-    коэффициент загрузки обслуживающей системы,

а также и другие характеристики ожидания.

 

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

Для анализа процесса, протекающего в СМО, существенно знать основные параметры системы: число каналов N, интенсивность потока заявок λ, производительность каждого канала (среднее число заявок μ, обслуживаемое каналом в единицу времени), условия образования очереди (ограничения, если они есть).

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

 

  (1‑1)

 

где l - интенсивность входящего потока (среднее число требований в единичном интервале)

m.- интенсивность потока обслуживания (среднее число требований, обрабатываемых каналом в единичном интервале)

 

Поскольку

 (1‑2)

и

 (1‑3)

 

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

 (1‑4)

 

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

 

Пример:

Если механизм доступа к файлу некоторой информационно-справочной системы в период наибольшей нагрузки обеспечивает 9000 обращений в час, а время одного обращения равно в среднем 300 мс, то коэффициент использования оборудования (механизма доступа к файлу) в час пиковой нагрузки составляет:

 

 

Понятие коэффициента использования оборудования используется довольно часто. Чем ближе коэффициент использования оборудования к 100%, тем больше задержки и длиннее очереди.

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

 

 (1‑5)

 

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

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

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

 

 

В первой строке указаны моменты времени прибытия клиента (время, прошедшее с момента начала наблюдения, приятого за 0).

Во второй строке — время, прошедшее с момента прибытия предыдущего клиента до момента прибытия клиента.

В третьей строке — время обслуживания клиента.

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

Для получения статистически значимых данных о реальном процессе потребовалась бы значительно большая выборка (см., например, раздел Ошибка! Источник ссылки не найден.), однако приблизительную оценку некоторых важных характеристик системы массового обслуживания можно получить и в данном случае. Как видно из данных таблицы, десять клиентов из пятнадцати ожидают. Среднее время ожидания для этих клиентов равно 49/10; среднее время ожидания для всех клиентов равно 49/15.

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

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

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

Например, отрезок, соответствующий второму клиенту, протянется от второй до пятой единицы времени, а отрезок, соответствующий третьему клиенту, — от шестой до двенадцатой единицы. Эти два отрезка не перекрываются. Однако отрезок, соответствующий четвертому клиенту, протянется от одиннадцатой до тринадцатой единицы времени и перекроется на единицу времени с отрезком, соответствующим предыдущему клиенту. Он перекроется также и с отрезком, соответствующим следующему клиенту.

 

 

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

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

 

Задание.

В работе требуется рассчитать показатели СМО по хронограмме процесса поступления и обслуживания требований в системе.

Для выполнения работы следует использовать табличный редактор Microsoft Excel.

1.   Откройте приложение Microsoft Excel.

Создайте листы с именами, как показано на рисунке ниже:

 

 

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

 

2.    На листе Таблица создайте таблицу.

 

 

в строки Текущее время и Время обслуживания занесите данные своего варианта (см. раздел 0).

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

 

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

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

 

 

4.   Перейдите на лист Диаграмма.

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

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

 

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

 

 

создав, например, отдельные таблицы для групп с числом заявок в очереди равным 0, 1, 2, …и занося значения времени начала (tн) и окончания (tк) каждого периода в соответствующие столбцы.

В столбцах DT следует записать выражение для подсчета разности (т.е., для продолжительности интервала).

В строке S(DТ) расчетной таблицы записываются суммы интервалов по каждой группе.

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

В строке i*Pi расчетной таблицы записываются произведения числа требований в очереди на их вероятности. Сумма этих произведений, записанная в ячейку столбца сумм, представляет собой величину средней длины очереди.

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

 

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

 

 

7.    Заполните итоговый перечень со значениями показателей на листе Таблица, поместив его под основной таблицей с исходными и расчетными данными:

 

 

Отчет по работе:

Отчет по работе должен включать:

-      Исходные данные в соответствии с описанной структурой таблицы.

-      Временную диаграмму процесса в СМО в соответствии с описанием.

-      Рассчитанные значения показателей.

 

Контрольные вопросы:

1)    Зачем нужно оценивать показатели СМО?

2)    Какими показателями можно характеризовать СМО с отказами?

3)    Какими показателями можно характеризовать СМО с неограниченной очередью?

4)    Какими показателями можно характеризовать СМО с ограниченной очередью?

5)    Что такое интенсивность входящего потока?

6)    Как найти интенсивность потока по данным наблюдения?

7)    Что такое интенсивность обслуживания?

8)    Как найти интенсивность обслуживания по данным наблюдения?

9)    Что показывает коэффициент загрузки канала?

10)   Как найти коэффициент загрузки канала по данным наблюдения? Привести несколько способов.

11)   Как определяется коэффициент простоя канала, как он связан с коэффициентом загрузки канала?

 

Задачи.

1)    В мастерской ремонта бытовой электронной техники работает один мастер по ремонту телевизоров. Интенсивность поступления телевизоров в ремонт составляет 4 телевизора за один рабочий день, время ремонта одного телевизора занимает половину рабочего дня. Ограничений на складские помещения нет. Справится ли данная мастерская с ремонтом телевизоров?

2)    Порт имеет один грузовой причал для разгрузки судов. Интенсивность потока судов составляет 0,5 судов в сутки. Среднее время разгрузки одного судна равно 1,5 суток. Найти коэффициент загрузки причала.

3)    Предприятие планирует покупку мобильных телефонных аппаратов. Сколько аппаратов предприятию необходимо закупить, если заявки от клиентов будут поступать с интенсивностью 80 заявок в час, а средняя продолжительность разговора будет составлять 2,8 мин?

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

5)    Вокзал имеет три платформы для местных поездов. В среднем за сутки к каждой платформе подходит 40 поездов. Среднее время стоянки у платформы составляет 4 мин. Определить характеристики вокзала.

 

Варианты хронограмм