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

Тип работы: Курсовая работа
Бесплатно: Антиплагиат
Объем: 63 страниц
В избранное:

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1 ЗАДАНИЕ

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

2. 1 Системы массового обслуживания.

2. 1. 1 Классификация систем массового обслуживания. . ….

2. 1. 2 Основные элементы системы массового обслуживания. .

2. 1. 3 Характеристики СМО

2. 2 Метод моделирования случайных чисел.

2. 2. 1 Метод вычетов (конгруэнтный метод)

2. 3 Моделирование специальных распределений. . . .

2. 3. 1 Нормальное распределение

2. 3. 2 Равномерное распределение. .

3 РАЗРАБОТКА АЛГОРИТМА .

3. 1. Блок - схема моделирующего алгоритма .

3. 2 Описание переменных. .

4 ОПИСАНИЕ ПРОГРАММЫ

4. 1 Общие сведения.

4. 2 Функциональное назначение

4. 3 Описание логической структуры программы

4. 4 Вызов и загрузка

4. 5 Используемые технические средства. .

4. 6 Входные данные

4. 7 Выходные данные.

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ . . .

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

Если 0< < , заявка, заставшая все линии занятыми в момент поступления, ожидает в течение в очереди, а по истечении этого времени получает отказ. Такие системы массового обслуживания называются системами с ограниченным ожиданием. Качество обслуживания в этом случае оценивается вероятностными характеристиками как количества отказов, так и времени ожидания, а иногда более сложными показателями, учитывающими обе эти стороны качества обслуживания.

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

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

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

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

1 ЗАДАНИЕ

Допустим, что в издательстве время от времени скапливаются большое количество рукописных материалов, которых необходимо набрать в текстовом редакторе MS Word. В издательстве работает k машинисток, которые занимаются набором текстов. Интервалы времени между прибытием новых рукописных материалов (заявок) представлены случайной величиной ƒ(τ) . Время набора текста - случайной величиной с плотностью распределения ψ(τ) . Таблица 1.

Издательство относится к СМО с ограниченной длиной очереди m.

Машинистки работают с 9. 00 до 18. 00 с перерывом на обед с 13. 00 до 14. 00 часов.

Руководство издательства интересуют следующие показатели эффективности работы машинисток:

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

Таблица 1

№ варианта

ƒ(τ)

ψ(τ)

№ варианта: 63

k: 4

ƒ(τ): Равн.

ψ(τ): Эксп.

m: 20-25

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

2. 1 Системы массового обслуживания

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

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

2. 1. 1 Классификация систем массового обслуживания

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

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

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

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

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

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

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

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

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

Кроме этих признаков, СМО делятся на два класса: “открытые” и “замкнутые”. В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО. В замкнутой СМО - зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока “требований” со стороны станков зависит от того, сколько их уже неисправно и ждет наладки. Это пример - замкнутой СМО. Классификация СМО далеко не ограничивается приведенными их разновидностями, но мы ограничимся ими.

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

Все перечисленные выше разновидности СМО исследуются в теории массового обслуживания.

2. 1. 2 Основные элементы системы массового обслуживания

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

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

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием ),

2) с отказами;

3) смешанного типа.

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

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

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

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

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

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

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

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

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

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

Простейший поток обладает такими важными свойствами:

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

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

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

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

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

вероятность того, что в обслуживающую систему за время t поступит именно k требований:

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

На практике условия простейшего потока не всегда строго выполняются. Часто имеет место не стационарность процесса (в различные часы дня и различные дни месяца поток требований может меняться, он может быть интенсивнее утром или в последние дни месяца) . Существует также наличие последействия, когда количество требований на отпуск товаров в конце месяца зависит от их удовлетворения в начале месяца. Наблюдается и явление неоднородности, когда несколько клиентов одновременно пребывают на склад за материалами. Однако в целом пуассоновский закон распределения с достаточно высоким приближением отражает многие процессы массового обслуживания. Почему такое предположение в ряде важных случаев оказывается верным, дает ответ общая теорема А. Я. Хинчина, которая представляет исключительную теоретическую и практическую ценность. Эта теорема имеет место в случае, когда входящий поток можно представить в виде суммы большого числа независимых потоков, ни один из которых не является сравнимым по интенсивности со всем суммарным потоком. Приведем “не строгую” формулировку этой теоремы (полная формулировка и доказательство приведены в) .

... продолжение

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.