Характеристика системы массового обслуживания, куда поступают заявки обслуживания. Особенности моделирования системы массового обслуживания. Имитация работы системы массового обслуживания с относительными приоритетами. Отчеты полного факторного плана.
Аннотация к работе
Системой массового обслуживания (СМО) называется система, на которую в случайные моменты времени поступают заявки, нуждающиеся в том или ином виде обслуживания в течение некоторого отрезка времени. Изза случайного характера потока заявок в системе, в какие-то моменты времени могут возникнуть очереди, а в другие моменты система может работать с недогрузкой или вообще простаивать. Имитационное моделирование - это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему и с ней проводятся эксперименты с целью получения информации об этой системе.
Введение
массовый обслуживание моделирование имитация
Системой массового обслуживания (СМО) называется система, на которую в случайные моменты времени поступают заявки, нуждающиеся в том или ином виде обслуживания в течение некоторого отрезка времени. Изза случайного характера потока заявок в системе, в какие-то моменты времени могут возникнуть очереди, а в другие моменты система может работать с недогрузкой или вообще простаивать. При проектировании СМО архитектор преследует цель увеличения ее КПД, и как следствие, увеличения прибыли, от использования системы.
Имитационное моделирование - это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему и с ней проводятся эксперименты с целью получения информации об этой системе.
Архитектор использует метод имитационного моделирования, для оценки эффективности. Это позволяет быстро и с наименьшими затратами собрать статистику и на ее основе оптимизировать систему.
Целью данной курсовой работы является моделирование системы массового обслуживания со следующими параметрами: Разработайте программу для имитационного моделирования системы массового обслуживания в соответствии с требованиями технического задания и исходными данными: Начальные значения параметров системы: дисциплина обслуживания - с относительным приоритетом на три значения;
количество устройств s = 6;
емкость накопителя l = 35;
среднее время поступления требований = 60 c;
среднее время обработки требований = 180 c.
Начальные значения коэффициентов экономической оценки: c1 = 6·106 руб.;
c2 = 7·104 руб.;
c3 = 6·103 руб.;
c4 = 0.23 руб.;
c5 = 0.099 руб.
Оценке подлежат следующие параметры: коэффициент использования системы ?;
среднее время ожидания заявки в очереди Tq;
среднее время пребывания заявки в системе Ts;
среднее по времени число требований в очереди Nq;
среднее по времени число требований в системе Ns;
абсолютная пропускная способность Ca;
относительная пропускная способность Cr.
Анализ задания и обзор аналогов. Анализ задания
Схема системы массового обслуживания представлена на рисунке 1.1
Рисунок 1.1 - Модель реализуемой системы
В данной курсовой работе требуется сымитировать работу СМО с относительными приоритетами. Это значит, что после освобождения одного из обслуживающих приборов из очереди к нему первым попадет заявка, имеющая более высокий приоритет. Всего имеется три значения приоритета.
В нашей системе имеется шесть обслуживающих приборов. Все они обслуживают заявки с одинаковой скоростью, со средним временем выполнения, равным 180 с. Цена одного прибора равна 6 000 000 р. Также, каждый обслуживающий прибор требует затраты на собственное содержание. Они равны 70 000 р в год для работающего прибора и 6 000 для простаивающего.
Максимальная длина очереди - 35. При поступлении заявок сверх данного ограничения в системе появляются издержки в размере 0.23 рубля. Среднее время поступления требований равно 60 с.
Обзор аналогов
СМО встречаются в нашей жизни постоянно. Очереди в кассе, обслуживание телефонных звонков, обслуживание клиентов в банке и.т.д.
Рассмотрим примеры СМО из металлургической промышленности
Примерами систем массового обслуживания без потерь в металлургической промышленности являются производственные системы металлургических цехов.
Производственные процессы в металлургических цехах должны быть организованы таким образом, чтобы производство было максимально эффективным. Неэффективность производства приводит к большим экономическим потерям. Для обеспечения эффективной работы производственных мощностей необходимо правильно выбрать их параметры. Параметры должны выбираться таким образом, чтобы мощности могли обслуживать случайный поток требований. Этим вопросом "занимается" теория массового обслуживания.
Примерами систем массового обслуживания в металлургии являются: Система подачи лома и чугуна в конвертор. Потребность сталеплавильного агрегата в этих материалах является потоком требований. Система подачи материалов должна обеспечить своевременную их загрузку в конвертор. Многоканальная СМО.
Машина непрерывного литья заготовок. Здесь потоком требований являются ковши со сталью, которые нужно разлить. Очень важным является правильный выбор количества МНЛЗ. Количество МНЛЗ рассчитывают, исходя из того, чтобы при работе методом "плавка на плавку" была обеспеченная синхронность работы машин непрерывного литья заготовок и сталеплавильных агрегатов. Многоканальная СМО.
Комплекс ковшового вакуумирования. Ковши со сталью являются потоком требований. Одноканальная, многофазная СМО (МСШ, установка "печь-ковш", вакуумная камера).
В данной курсовой работе будет разработана следующая система: Сервис выполнения сложных математических расчетов
Имеется три группы пользователей: SUPERVIP, VIP и обычные пользователи. Ожидается, что количество пользователей в каждой группе приблизительно равно, поэтому заявки с каждым приоритетом будут поступать с одинаковой вероятностью, равной 1/3. Каждый из них может отсылать на сервер запрос на выполнение операции, который в свою очередь пересылает эти запросы на обслуживающие компьютеры, а в случае отсутствия свободных, организовывает очередь, в которой следующий, обрабатываемый запрос будет определен, в зависимости от группы пользователя. Размер памяти компьютера, который организовывает очередь очень мал, поэтому длина очереди ограничена 35 заявками. При невыполнении заявки фирма платит клиенту неустойку в размере 0.23 рублей.
Схему данного сервиса можно увидеть на рисунке 1.2
Под потоком событий в теории вероятностей понимается последовательность событий, происходящих одно за другим в какие-то моменты времени. Опишем несколько свойств потока событий.
Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени определенной длины зависит только от длины этого участка и не зависит от того, где именно на оси времени он расположен.
Поток событий называется потоком без последействия, если для любых неперекрывающихся участков времени число событий, попадающих на один из них, не зависит от числа событий, попадающих на другие.
Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Поток, обладающий всеми вышеперечисленными свойствами, называется простейшим потоком. Именно при помощи такого потока описывается поступление заявок в СМО.
Для моделирования простейшего потока используется экспоненциальное распределение.
Экспоненциальное или показательное распределение - абсолютно непрерывное распределение, моделирующее время между двумя последовательными свершениями одного и того же события.
Плотность случайной величины х, распределенной экспоненциально имеет вид: , (2.1) где лямбда - обратный коэффициент масштаба.
Функция экспоненциального распределения имеет вид: (2.2)
Для генерации экспоненциальной случайной величины воспользуемся методом обратного преобразования:
(2.3)
, где: U - непрерывное равномерное распределение [0, 1];
Логика работы. Блок-схемы алгоритмов
Общий алгоритм работы системы представлен на рисунке 3.1
Рисунок 3.1 - Логика работы системы
Алгоритм работы системы в единицу времени представлен на рисунке 3.2
Рисунок 3.2 - Логика прохода единицы времени
На рисунке 3.3 представлен алгоритм добавления заявки в систему.
Рисунок 3.3 - Логика добавления заявки
Интерфейс системы
Для реализации системы использовались следующие технологии: Язык программирования Python 2.7
Графические средства фреймворка QT для создания интерфейса программы
Библиотека NUMPY для математических вычислений
Библиотека matplotlib для рисования графиков
Внешний вид интерфейса системы можно увидеть на рисунке 3.1
Рисунок 3.1- интерфейс программы
На рисунке 3.2 представлен график зависимости количества заявок от времени их выполнения. По этому графику видно, что данная случайная величина распределена по экспоненциальному закону распределения.
Рисунок 3.2 - зависимость количества заявок, от времени их выполнения
На рисунке 3.3 представлен график зависимости количества заявок от времени их появления. По этому графику видно, что данная случайная величина также распределена по экспоненциальному закону распределения.
Рисунок 3.3 - зависимость количества заявок от времени их появления
На рисунке 3.4 представлены графики зависимостей среднего и общего числа заявок в очереди от времени. По этим графикам можно судить о небольшом количестве заявок в очереди.
Рисунок 3.4 - Зависимость среднего и общего числа заявок в очереди от времени
На рисунке 3.5 представлены графики зависимостей среднего и общего числа заявок в системе от времени. По этим графикам можно судить о достаточно небольшом количестве заявок в системе по сравнению с размером очереди.
Рисунок 3.5 - Зависимость среднего и общего числа заявок в системе от времени
На рисунке 3.6 представлен график зависимости коэффициента использования системы от времени. По нему можно судить о недостаточной загруженности системы при данных входных параметрах
Рисунок 3.6 - Зависимость коэффициента использования системы от времени
Предварительные прогоны системы
Для анализа выходных параметров моделирования необходимо рассчитать количество экспериментов для построения факторного плана. Расчет количества экспериментов производится по формуле: , (4.1) где
- дисперсия;
- 5% от математического ожидания на 10 значениях каждого выходного параметра;
=1.96 - квантиль порядка .
Для этого проведем 10 экспериментов с данными значениями. Результаты прогонов представлены в таблице 4.1
A - начальное значение генератора случайной величины поступления требования;
S - начальное значение генератора случайной величины обработки требования;
p - коэффициент использования системы;
d - среднее время ожидания в очереди;
w - среднее время нахождения заявки в системе;
Q - среднее по времени число требований в очереди;
L - среднее по времени число требований в системе;
R - количество необслуженных заявок (в процентах)
Возьмем число прогонов для каждого плана равным 81.
Построение факторного плана
По результатам 10 тестовых прогонов можно судить о том, что система используется недостаточно. Поэтому при построении факторного плана будем стремиться увеличить коэффициент использования системы. Этого можно добиться убрав один из компьютеров (сократить число устройств), увеличив среднее время выполнения заявки (закупив более слабые компьютеры для системы) или уменьшив среднее время поступления заявки (увеличить использование системы, например, проведя рекламную кампанию).
Уровни факторов и их значения представлены в таблице 4.2
Таблица 4.2 - уровни факторов и их значения
Фактор -
Количество устройств (m) 5 6
Среднее время поступления требования, 40 60
Среднее время обработки требования, 180 210
Для планирования экспериментов был построен факторный план , значения которого приведены в таблице. Результаты всех прогонов приведены в приложении А.
L -10,0783 39,9064 -3,898 -7,55537 -0,39313 0,8877 -0,393
I -2,30E 07 9E 07 -7E 06 -1,80E 07 71244,7 1E 06 71245
Регрессионный анализ - это метод установления аналитического выражения стохастической зависимости между исследуемыми признаками. Уравнение регрессии показывает, как в среднем изменяется у при изменении любого из xi.
Общий вид уравнения регрессии представлен ниже: , (4.9)
где - коэффициенты уравнения регрессии
Расчет коэффициентов будет проводиться матричным методом.
Представим данные наблюдений и коэффициенты модели в матричной форме.
(4.10)
Здесь Y - n-мерный вектор-столбец наблюдений зависимой переменной; X - матрица размерности n х (m 1), в которой i-я строка i = 1, 2,..., n представляет i-е наблюдение вектора значений независимых переменных X1, X2,...,Xm, единица соответствует переменной при свободном члене b0; B - вектор-столбец размерности (m 1) параметров уравнения множественной регрессии; e - вектор-столбец размерности n отклонений выборочных значений yi зависимой переменной от значений yi, получаемых по уравнению регрессии: (4.11)
В матричном виде соотношение примет вид: (4.12)
Согласно методу наименьших квадратов: (4.13) где ET = (e1, e2,…, en), т. Е. надстрочный значок T означает транспонированную матрицу.
Можно показать, что предыдущее условие выполняется, если вектор-столбец коэффициентов B найти по формуле: (4.14)
Здесь XT - матрица, транспонированная к матрице X, (XTX)-1 - матрица, обратная к (XTX). Соотношение справедливо для уравнений регрессии с произвольным количеством m объясняющих переменных.
Значения коэффициентов уравнения регрессии представлены в таблице 4.5. Расчеты проводились в Microsoft Excel.
Таблица 4.5 - значения коэффициентов уравнения регрессии. p d W Q L I
Рекомендации по использованию результатов моделирования
Как мы видим из полученных результатов, изначальные параметры системы не являются оптимальными, изза низкого коэффициента использования системы. Если владелец системы ставит перед собой задачу минимизации экономической оценки, то ему следует воспользоваться планом с 5 устройствами, 180 секундами обработки заявки и 60 секундами поступления. При таких входных параметрах можно ожидать следующие выходные: 0.6 - коэффициент использования системы, 21.1 - время ожидания в очереди, 201.3 - среднее время нахождения заявки в системе, 0.35 - среднее по времени число требований в очереди, 3.37 - среднее по времени число требований в системе, 5509287 - экономическая оценка, 0 процентов необслуженных заявок.
Относительно базовых входных параметров мы получаем снижение затрат при незначительном увеличении среднего времени нахождения заявки в очереди и системе. Если владелец системы ставит цель установить коэффициент использования приблизительно равным 0.8, то ему следует воспользоваться планом с 6 устройствами, 180 секундами обработки заявки и 40 секундами поступления новых. Выходные параметры в этом случае будут следующие: 0.74 - коэффициент использования системы, 46,1 - время ожидания в очереди, 225,57 - среднее нахождение заявки в системе 1,16 - среднее по времени число требований в очереди, 5,63 - среднее по времени число требований в системе, 8456149 - экономическая оценка, 0 процентов необслуженных заявок. Во втором плане мы видим увеличение коэффициента использования, при небольших увеличениях времени ожидания и экономической оценки.