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

Министерство образования и науки Республики Казахстан

Карагандинский Государственный Технический Университет

Кафедра ____САПР______

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

По дисциплине: ”Прикладная теория систем”

Тема: "Разработка иммитационной модели системы

массового обслуживания"

 

 

Руководители

(подпись) (дата)

Студент

(подпись) (дата)

2009

Содержание

 

Введение

1. Техническое задание

2. Теоретическая часть

2.1 Предмет и задачи теории массового обслуживания

2.2 Классификация СМО

2.3 Характеристики СМО

2.4 Концептуальная модель СМО

2.5 Актуальность работы

2.6 Существующие алгоритмы решения

2.7 Технические требования

2.7.1 Общие требования

2.7.2 Центральный процессор

2.7.3 Материнская плата

2.7.4 Оперативная память

2.7.5 Видеоадаптер

2.7.6 Монитор

2.7.7 Жесткий диск

2.7.8 Клавиатура

2.7.9 Мышь

3. Практическая часть

3.1 Выбор среды разработки программирования

3.2 Выбор алгоритма решения

3.3 Структура программы

3.4 Результаты экспериментов

3.5 Руководство пользователю

Заключение

Список используемой литературы

Введение

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

В задачи курсового проекта входит:

получение знаний в области прикладной теории систем;

выработка способности системного рассмотрения проблем и задач;

развитие навыков программирования, полученных на предыдущих курсах;

написание программы, соответственно варианту задания.

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

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

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

1. Техническое задание

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

В интерфейсе программы предусмотреть возможность ввода параметров:

время моделирования;

число потоков заявок и параметры каждого потока (приоритет, min и max интервал генерирования);

число аппаратов обслуживания;

число очередей и max время пребывания заявки в очереди;

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

Результаты работы программы должны включать:

на каждом шаге отображать модельное время;

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

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

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

По заданию аппаратами выступают процедуры (всего в поликлинике может быть от 3 до 9 процедур). Каждому больному могут назначать несколько процедур из списка возможных. Устанавливается время ожидания заявки в очереди, периодичность прихода клиентов, время обслуживания каждой процедуры (от 5 до 60 минут), максимальная длина очереди, количество процедур для пациента. Определить оптимальное число процедур для более эффективного обслуживания всех пациентов.

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

2. Теоретическая часть 2.1 Предмет и задачи теории массового обслуживания

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

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

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

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

Система обслуживания считается заданной, если известны:

1) поток требований, его характер;

2) множество обслуживающих приборов;

3) дисциплина обслуживания (совокупность правил, задающих процесс обслуживания).

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

2.2 Классификация СМО

Существует большое количество различных моделей СМО и методов их классификации.

Рисунок 2.1 - Классификация СМО

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

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

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

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

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

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

2.3 Характеристики СМО

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

•среднее время обслуживания;

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

•среднее время пребывания в СМО;

•средняя длина очереди;

•среднее число заявок в СМО;

•количество каналов обслуживания;

•интенсивность входного потока заявок;

•интенсивность обслуживания;

•интенсивность нагрузки;

•коэффициент нагрузки;

•относительная пропускная способность;

•абсолютная пропускная способность;

•доля времени простоя СМО;

•доля обслуженных заявок;

•доля потерянных заявок;

•среднее число занятых каналов;

•среднее число свободных каналов;

•коэффициент загрузки каналов;

•среднее время простоя каналов.

2.4 Концептуальная модель СМО

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

Рисунок 2.2 – Концептуальная модель СМО

2.5 Актуальность работы

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

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

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

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

2.6 Существующие алгоритмы решения

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

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

б) Если же при поступлении требования свободных приборов нет, возможны два варианта:

требование тут же покидает систему, получает "отказ" - система с отказами;

требование остается ожидать освобождения прибора - система с ожиданием.

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

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

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

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

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

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

a) за время t требование начало обслуживаться, но обслуживание еще не закончено - потеря "недообслуженного" требования;

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

3) На длину очереди - требование, застав очередь длины k, остается в ней с вероятностью P_k и не присоединяется к очереди с вероятностью g_k=1 - P_k,'. именно так обычно ведут себя люди в очередях.

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

Некоторые возможные и встречающиеся на практике правила:

4) Время обслуживания требования зависит от того, сколько ему пришлось ожидать.

5) Среднее время обслуживания уменьшается с ростом очереди.

6) Число приборов возрастает с ростом очереди.

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

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

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

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

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

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

выбор свободного прибора;

задание времени обслуживания.

Для системы с отказом 1) и 2) исчерпывают весь процесс обслуживания. Если рассматриваются системы массового обслуживания с ожиданием, то должны быть дополнительно заданы правила:

образования очереди;

назначения очередного требования.

 

2.7 Технические требования 2.7.1 Общие требования

Выбор технического обеспечения обуславливается следующими основными параметрами:

производительность. Комплекс технических средств должен удовлетворять требованиям, предъявляемым программным обеспечением;

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

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

Комплекс технических средств должен быть построен на базе ПЭВМ IBM PC или совместимых с ней.

В качестве средств программной обработки данных следует использовать ПЭВМ с процессором типа Intel Celeron (либо Intel Pentium) с тактовой частотой не менее 500 МГц.

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

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

Для отображения информации, выводимой во время работы, необходим монитор с разрешающей способностью не менее 1024x768 и поддержкой отображения 16,5 млн. цветовых оттенков.

2.7.2 Центральный процессор

Центральный процессор должен обеспечивать удовлетворительную работу операционной системы Windows 98/2000/XP, среды разработки проекта (AutoCAD) и самого проекта. В связи с этим для разрабатываемой системы рекомендуется использовать процессор Pentium IV, обладающий достаточной производительностью, надежностью, низкой стоимостью и низким энергопотреблением. В сравнении с процессором Celeron^TM