Имитационного моделирования систем с приоритетным обслуживанием и отказами

Оглавление

             Введение………………………………………………………………...…..2                                 

        Глава  I. Теоретические основы имитационного моделирования систем с приоритетным   обслуживанием и отказами……………………………………3

        1.1. Методика определения приоритетов обслуживания заявок……......3

        1.2. Одноканальные СМО с неоднородным потоком заявок…................7

             1.2.1. Характеристики и свойства ДО БП……………………………..9

             1.2.2. Характеристик и свойства ДО ОП……………………………...11

            1.2.3. Характеристики и свойства ДО АП……………………………..14

      1.3. Система массового обслуживания с отказами ………........................16

      1.4. Особенности имитационного моделирования систем массового обслуживания……………………………………………………………………19

         Глава II. Построение  имитационной модели на языке GPSS World.…….26

        2.1. Постановка задачи………………………………………………......... 26  

        2.2. Функциональная схема..........................................................................27

        2.3 Создание ИМ на языке GPSS…………………………………………28

        2.4. Анализ результатов моделирования…………………………………32

        Заключение…………………………………………………………………35

       Список литературы …………………………………………………….….36

       Приложение 1…………………………………………………..…………..37

       Приложение 2………………………………………………………………38

 

Введение.

Формальное описание процессов  в виде системы массового обслуживания широко применяется в самых различных областях науки и практики. Теоретической базой построения и исследования СМО является теория массового обслуживания (ТМО).         Теория массового обслуживания – это область прикладной математики, занимающаяся анализом процессов в СМО, в которых события повторяются многократно. С помощью этой теории разрабатываются методы решения типовых задач массового обслуживания, строятся модели СМО и определяются их количественные характеристики.      Предметом теории массового обслуживания является установление зависимостей между характером потока заявок, числом каналов обслуживания, производительностью отдельного канала и эффективным обслуживанием с целью нахождения наилучших путей управления этими процессами. Задачи теории массового обслуживания носят оптимизационный характер и в конечном итоге включают экономический аспект по определению такого, варианта системы, при котором будет обеспечен минимум суммарных затрат от ожидания обслуживания, потерь времени и ресурсов на обслуживание и от простоев каналов обслуживания.    Методами ТМО анализируют функционирование объекта, а затем решают вопрос о синтезе обслуживающих устройств и  выборе оптимальных параметров системы.            Целью данного курсового проекта является создание имитационных моделей системы с приоритетным обслуживанием и отказами  средствами систем имитационного моделирования GPSS World.     Задачей курсовой работы - ознакомление с современными концепциями построения моделирующих систем, с основными приемами имитационного моделирования, встраиваемыми в общую процедуру преобразования информации от структурирования и формализации составляющих предметных областей до интерпретации обработанных данных и приобретенных знаний, связанных с описанием экономических процессов. Данная работа представляет собой работу по созданию и реализации модели системы массового обслуживания для получения необходимых нам результатов на основании исходных данных.     Методологической и теоретической основой при написании работы послужила учебная литература и труды отечественных и зарубежных авторов.

 

Глава I. Теоретические  основы моделирования с приоритетным   обслуживанием и отказами.

1. Методика определения приоритетов обслуживания заявок.

На практике часто приходится сталкиваться  с системами специального вида, которые предназначены для  многоразового использования при  выполнении однотипных задач. Процессы подобного рода называют процессами обслуживания, а системы - системами  массового обслуживания. Примерами  таких систем являются различные  системы связи, ремонтные мастерские, вычислительные комплексы, объекты  из сферы обслуживания.            Каждая система обслуживания может иметь возможность одновременного обслуживания нескольких поступивших требований, или заявок. Каждую из обслуживающих единиц  СМО называют каналом. По числу обслуживающих каналов в СМО подразделяют на одноканальные и многоканальные.           СМО делят на два основных типа: системы с отказами и системы с ожиданием. Отказы в СМО появляются по двум основным причинам: либо отсрочка обслуживания для поступающих заявок невозможна, либо в СМО отсутствуют свободные места для ожидания (или их вообще нет).   По дисциплине очереди (т.е. по критерии выбора из очереди очередной заявки)  СМО подразделяются на системы с приоритетом и без приоритета. В первом случае заявке, пришедшей в СМО, присваивается некоторый приоритет, в соответствии с которым на обслуживание оправляется заявка с наивысшим приоритетом, несмотря на то, что возможно, она пришла в систему после прихода прочих заявок. В этом случае на самом деле образуется несколько очередей с разным уровнем приоритета. При реализации дисциплины очереди - без приоритета возможны различные правила отбора заявок на обслуживание: первый пришел первый обслужен, последний пришел -  первый обслужен или в случайном порядке (например, с заданными вероятностями выборки из очереди).      Системы с приоритетом, в свою очередь, могут подразделяться на СМО с прерыванием и без прерывания. В системах с прерыванием заявка с высшим приоритетом прерывает обслуживание заявки с более низким приоритетом. Прерванная заявка может быть поставлена в очередь и, возможно, когда – нибудь будет обслужена в соответствии со своим приоритетом.          Потребность построения эффективного алгоритма организации обслуживания заявок  приводит к необходимости присвоения им некоторых признаков, которые обычно называются приоритетами.     Заявки на обслуживание поступают в СМО в случайные моменты времени и становятся в очередь. При этом возникает вопрос, в какой последовательности их обслужить? Как раз здесь вступает в действие система приоритетов. Но остается неясным принцип присвоения приоритетов. Эти принципы могут быть  различными. Вот один из возможных алгоритмов реализации подобной задачи:      - на основании анализа характеристик заявок на обслуживание (обслуживаемых задач) устанавливается множество параметров этих заявок (задач) и элементам множества придаются некоторые значения;     - в соответствии со значениями элементов множества параметров выбираются методы упорядочения выполнения заявок (задач);     - сравниваются варианты упорядочения заявок (задач) по различным элемента множества параметров;          - разрабатывается правило использования выбранного метода и оценивается его эффективность.        Предположим, удалось выделить несколько элементов множества признаков . Пусть это будут, например, следующие характеристики: потребный ресурс на выполнение данной заявки, отношения с заказчиком (с источником заявки), характеристика срочности выполнения заявки, ожидаемая прибыль и так далее. Порядок учета признаков пусть соответствует номерам индексов признаков Элементам множества X придаются некоторые значения, например, соответствующие смыслу, или важности, или весу этих элементов. Принцип учета элементов множества Х заключается в придании элементам значений , равных 0 или 1. Пусть значение 1 соответствует случаю, когда отдается предпочтение большему по абсолютному значению элементу множества Х, а 0 – меньшему. Методику использования элементов множества признаков можно пояснить на примере. Пусть используется три (=3) элемента множества Х: Причем В очереди на обслуживание находится, например, 5 заявок и приняты следующие значения элементов множества Х для каждой заявки:         ,            ,                     =3,      =0,4,                         Индекс в скобках относим значение параметров к одной из рассматриваемых заявок.          Выбор последовательности заявок для реализации происходит следующим образом. При анализе по первому элементу множества Х будут выбраны 1, 2 и 4 заявки. При анализе по второму элементу множества Х – 1 и 2 заявки. А при анализе по третьему элементу окончательно будет выбрана 2-я заявка. На следующем этапе (осталось 4 заявки), уже после анализа по второму элементу будет выбрана 1-я заявка. После этого ужу на первом этапе будет выбрана 4-я заявка. Остается выбрать последовательность выполнения 3-й и 5-й заявок. При анализе по   не удается ничего выбрать, так как  и и только при анализе по элементу первой будет выбрана 5-я заявка. И последней выполняется оставшаяся 3-я заявка. Таким образом, установлена следующая последовательность выполнения заявок:  2, 1, 4, 5, 3.     Что можно сказать о таком подходе к выбору приоритетов обслуживания? Во-первых,  очереди может находиться в разное время различное количество заявок, ожидающих присвоения приоритета и начала обслуживания. Во-вторых, сам алгоритм выбора последовательности выполнения заявок (алгоритм присвоения приоритетов) довольно громоздкий и на свою реализацию может потребовать некоторый вычислительный ресурс, возможно сравнимый с получаемым выигрышем. И в - третьих, для реализации подобного алгоритма присвоения приоритетов нужен предварительный модельный эксперимент для подбора элементов, множества Х, выбора порядка их упорядочения, значения этих элементов и принципа их учета. Если же все эти препятствия  преодолены, то в некоторых случаях он может дать значительный эффект.      Возможен и иной подход к определению приоритетов на обслуживание заявок. Он основан на учете некоторых рассчитываемых случайных факторов. Пусть при формировании очереди заявок на обслуживание  учитываются два фактора , принимающие значения 0 или 1. Можно сказать, что формируется случайный вектор приоритетов Z,  включающий две компоненты  , то есть вектор Z (.  Первая компонента принимает два значения (например, существует возможность предоплаты) и   (возможность предоплаты отсутствует). Компонента также может принимать два значения  (например, существует договор на обслуживание заявок заказчика)  и (договора нет).     Закон распределения вектора Z  удобно задать в виде табл. 1.               Табл.1.

	P (	P (
	P(	P (

2. Здесь P ( вероятность совместного появления компонент (например, есть предоплата и договор);       P (  вероятность совместного появления компонент (например, есть предоплата, но нет договора);       P (  вероятность совместного появления компонент    (например, нет предоплаты, но есть договор);      P ( вероятность совместного появления компонент (например, нет предоплаты, и нет договора).      Вероятности P ( P (  P (  P (   могут вычисляться на основе анализа статистического материала (табл.1.1). Здесь кроме вышеперечисленных факторов учитывается отказ в обслуживании.                      Табл.1.1.

Данные об обслуживании по  кварталам
Квартал	Общее число заявок	По договору	По предоплате	Получили отказ	Прочие заявки
1	1856	920	400	37	499
2	2004	883	671	49	401
3	1639	764	528	23	324
4	1922	952	594	34	342
Итого за год	7421	3519	2193	143	1566

3. Считается, что заявки получают отказ, например, в случаях:     - предлагается не предоплата, а бартер;        - предоплата составляет мене 50%, а в базе надежности у заказчика неважная характеристика (или вообще отсутствует в базе);     - нет достаточного вычислительного ресурса для качественного обслуживания заявки.          Можно рассчитать вероятности событий с учетом сведений табл.1.1. Для этого сначала рассчитываются вероятности для компоненты      P ( ;       P (        Получена таблица распределения первой компоненты    (табл.1.2.).             Табл. 1.2.

P	0,47	0,53

4. Затем рассчитываем вероятности для компоненты   (из табл.1.1.).    P (         P (        Получена таблица для второй компоненты (табл.1.3.)               Табл.1.3.

P	0,30	0,70

5. Теперь можно рассчитать вероятности событий для табл. 1.1.     P (      P (      P (      P (     Таким образом, распределение вектора Z для приведенных статических данных можно свести в табл. 1.4.                   Табл.1.4.

	0,14	0,33
	0,16	0,37

6. Исходя из полученных результатов при имитационном моделировании реальной СМО, заявке присваивается наивысший (нулевой) приоритет, если и первый приоритет и   второй  приоритет и и третий приоритет и     В итоге  заявки, приходящие на вход с одновременным распределением интервалов времени поступления, выстраиваются в очередь, длительность пребывания в которой определяется двумерным законом распределения (табл.1.4) Количество учитываемых параметров при моделировании приоритетов может быть и больше. Если, например, переменные принимают по три возможных значений, то число приоритетов будет равна 9. Если учитывается три фактора (Z()) при двух значениях каждого из них, то равно 12. Если 3 при трех значениях каждого, то - 27 и так далее. Число моделируемых приоритетов может увеличиваться, но методика их задания, усложняясь, сохраняется.

1.2. Одноканальные СМО с неоднородным потоком заявок.

Рассмотрим одноканальную СМО с неоднородным потоком заявок, в которую поступили H классов заявок, образующие простейшие потоки с интенсивностями Длительность обслуживания заявок класса k распределена по произвольному закону со средним значением   и коэффициентом вариации Выбор заявки из очереди на обслуживание осуществляется в соответствии с заданной дисциплиной обслуживания, в качестве которой будем рассматривать: 

• Дисциплину обслуживания бесприоритетную (ДО БП), при которой заявки выбираются на обслуживание в порядке поступления;
• Дисциплину обслуживания заявок с относительными приоритетами (ДО ОП);
• Дисциплину обслуживания заявок с абсолютными приоритетами (ДО АП).

В качестве основной характеристики, описывающей эффективность функционирования системы, будем рассматривать средние времена ожидания заявок разных  классов, на основе, которой легко могут быть рассчитаны все остальные характеристик с использованием фундаментальных зависимостей.         При этом следует иметь виду, что представленные ниже формулы были получены при следующих предположениях:       1) СМО содержит один обслуживающий прибор, который в каждый момент времени может обслужить только одну заявку;     2) СМО имеет накопитель заявок неограниченной емкости, что означает отсутствие отказов поступающих заявкам при их постановке в очередь, то есть любая поступающая заявка всегда найдет в накопителе место для ожидания независимо от того, сколько заявок уже находится в очереди;              3) заявки разных классов, поступающие в СМО независимо друг от друга, образуют простейшие потоки;         4) длительности обслуживания заявок каждого класса в приборе распределены по произвольному закону и не зависят друг от друга;   5) обслуживающий прибор не простаивает, если в системе (накопителе) имеется, хотя бы одна заявка любого класса, причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка в соответствии с заданной дисциплиной обслуживания;   6) при использовании ДО ОП заявки разных классов выбираются на обслуживание только в зависимости от времени поступления в систему по правилу «раньше пришел – раньше обслужен», независимо от номера класса, к которому принадлежит заявка;         7) при использовании приоритетных дисциплин (ДО ОП и ДО АП) приоритеты классам заявок назначены по принципу «класс с меньшим номером имеет более высокий приоритет», то есть наивысшим приоритетом обладают заявка класса 1;          8) в случае ДО АП заявка, обслуживание которой прервано более высокоприоритетной заявкой, возвращает в накопитель, где ожидает дальнейшего обслуживания, причем ее обслуживание продолжается с прерванного места.

1.2.1. Характеристики  и свойства ДО БП.

При бесприоритетной  ДО средние времена ожидания одинаковы  для всех классов и определяются по следующей формуле:                                         (1.1) где суммарная загрузка системы.   Выражение (1.1)  получено в предположении, что в системе существует, стационарный режим отсутствует перезагрузка:      Анализ  аналитической зависимости позволяет выявить свойства ДО БП и сформулировать следующие выводы.       1. Среднее время ожидания заявок разных классов при использовании ДО БП при любых интенсивностях поступления и законах распределений длительностей обслуживания заявок: для всех Отметим, что средние времена пребывания в системе заявок разных классов, в общем случае, различны, так как различны длительности обслуживания: .     2. Среднее время ожидания заявок в очереди минимально при постоянной (детерминированной) длительности обслуживания заявок каждого класса, когда коэффициент вариации длительности обслуживания и увеличивается с ростом коэффициента вариации (дисперсии) длительности обслуживания. Заметим, что зависимость среднего времени ожидания от коэффициента вариации носит линейный характер. Так, например, при экспоненциально распределенной длительности обслуживания,  когда среднее время ожидания заявок увеличивается в 2 раза, а при в 5 раз, по сравнению с детерминированным обслуживанием.            3. Среднее время ожидания заявок существенно зависит от суммарной нагрузки Y (загрузки R) системы (рис. 1.1,а). При время ожидания заявок всех классов возоастает неограниченно: то есть заявки могуи ожидать обслуживания сколь угодно долго. Отметим, что увелечение суммарной нагрузки может быть обусловлено двумя факторами: увелесением интесивности поступления в систму заявок разных классов или увеличением длительности обслуживания заявок (например, за счет уменьшения скорости работы обслуживающего прибора).   Зависимость среднего времени пребывания в системе заявок разных классов от суммарной нагрузки аналогтчна зависимости времени ожидания (рис.1.1, б). Единственное отличие состоит в том, что средние времена пребывания в системе заявок разных классов, в общем случае, различны, то есть поэтому на графике, в отличие от времени ожидания, могут отображаться несколько зависимостей. Это различие обусловлено различием длительностей обслуживания заявок разных классов.