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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КУРСОВАЯ РАБОТА

По дисциплине: Основы моделирования биологических процессов и систем

Тема «Разработка экспертной системы на основе метода моделирования (системы массового обслуживания)»

Содержание

Введение

. Теория систем массового обслуживания

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

.1.1 Компоненты СМО

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

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

.2.1 Одноканальная СМО с отказами

.2.2 Одноканальная СМО с ожиданием и ограниченной очередью

.2.3 Одноканальная СМО с ожиданием и неограниченной очередью

.2.4 Многоканальная СМО с отказами

.2.5 Многоканальная СМО с ожиданием

. Разработка СМО для лечебно-профилактического центра

.1 Графическое представление СМО регистратуры лечебно-профилактического центра

.2 Логическая схема работы регистратуры лечебно-профилактического центра

.3 Процесс функционирования СМО

Заключение

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

Введение

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

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

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

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

Модели СМО очень распространены и применяются во многих сферах деятельности человека и реализуются при помощи вычислительных систем.

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

1. Теория систем массового обслуживания

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

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

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

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

Примерами систем массового обслуживания могут служить:

1.      магазины;

2.      банки;

.        почтовые отделения;

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

1.1.1 Компоненты СМО

Основными компонентами системы массового обслуживания любого вида являются:

1.      входной поток поступающих требований или заявок на обслуживание;

2.      дисциплина очереди;

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

Раскроем содержание каждого из указанных выше компонентов.

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

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

первым пришел - первый обслуживаешься;

пришел последним - обслуживаешься первым;

случайный отбор заявок;

отбор заявок по критерию приоритетности;

ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»).

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

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

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

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

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

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

2.      вероятностным распределением времени продолжительности обслуживания;

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

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

.        дисциплиной очереди;

.        мощностью источника требований.

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

1.  вероятность немедленного обслуживания поступившей заявки;

2.      вероятность отказа в обслуживании поступившей заявки;

.        относительная и абсолютная пропускная способность системы;

.        средний процент заявок, получивших отказ в обслуживании;

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

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

.        средний доход от функционирования системы в единицу времени и т.п.

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

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

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

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

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

СМО с ожиданием делятся на:

системы с ограниченным ожиданием,

системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

длина очереди;

время пребывания в очереди.

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

Все СМО различают по числу каналов обслуживания:

одноканальные системы;

многоканальные системы.

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

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

.2.1 Одноканальная СМО с отказами

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

,

где λ - интенсивность поступления заявок в систему (среднее число заявок, поступающих в систему за единицу времени).

Плотность распределения длительностей обслуживания:

,

где  - интенсивность обслуживания,_об - среднее время обслуживания одного клиента.

Пусть система работает с отказами. Можно определить абсолютную и относительную пропускную способность системы.

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

Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал обслуживания занят»:

.

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

.2.2 Одноканальная СМО с ожиданием и ограниченной очередью

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т.е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Рассмотрим систему с ограниченной очередью. Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), из которых одна обслуживается, а (N-1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.

Обозначим  - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:

,

Здесь ρ= - приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна:

,

С учетом этого можно обозначить

,

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):

вероятность отказа в обслуживании заявки:

_отк=Р_N=,

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

,

средняя продолжительность пребывания клиента (заявки) в очереди:

.

среднее число заявок (клиентов) в очереди (длина очереди):

.2.3 Одноканальная СМО с ожиданием и неограниченной очередью

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

Устойчивое решение в такой системе существует только тогда, когда λ<μ, то есть заявки должны обслуживаться с большей скоростью, чем поступают, в противном случае очередь может разрастись до бесконечности.

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

где r =  <1.

Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:

среднее число находящихся в системе клиентов (заявок) на обслуживание:

,

средняя продолжительность пребывания клиента в системе:

,

среднее число клиентов в очереди на обслуживание:

,

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

.

.2.4 Многоканальная СМО с отказами

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

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

.2.5 Многоканальная СМО с ожиданием

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

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

.

Решение будет действительным, если выполняется следующее условие:

Остальные вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием и неограниченной очередью определяется по следующим формулам:

среднее число клиентов в очереди на обслуживание:

,

среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди):

_S=L_q+ρ,

средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди:

,

средняя продолжительность пребывания клиента в системе:

.

2. Разработка СМО для лечебно-профилактического центра

В регистратуре лечебно-профилактическом центре (ЛПЦ) имеется 3 окна выдачи талонов для посещения различных врачей. Продолжительность обработки заявок в разных окнах характеризуется интервалами времени:  мин,  мин,  мин. Регистратура работает в 2 смены, с 8.00-14.00 и 14.00-20.00. Пациенты в поликлинику приходят с 8.00-14.00 час через интервалы времени  мин, с 14.00-20.00 час. - . смоделировать процесс работы 1-ой и 2-ой смены регистратуры ЛПЦ. Определить характеристики СМО.

.1 Графическое представление СМО регистратуры лечебно-профилактического центра

Графическое представление работы регистратуры в терминах СМО показано на рисунке 2.1.

Рисунок 2.1 - Структурная схема

Н1 - очередь на выдачу талонов к терапевтам (1 окно регистратуры),

Н2 - очередь на выдачу талонов к узким специалистам (кардиологу, хирургу, лору, офтальмологу, невропатологу) (2 окно регистратуры),

Н3 - очередь на выдачу талонов к узким специалистам (эндокринологу, гинекологу, урологу, онкологу) (3 окно регистратуры),

К1 - канал для приема заявок и выдачи талонов к терапевтам (1 окно регистратуры),

К2 - канал для приема заявок и выдачи талонов к узким специалистам (кардиологу, хирургу, лору, офтальмологу, невропатологу) (2 окно регистратуры),

К3 - канал для приема заявок и выдачи талонов к узким специалистам (эндокринологу, гинекологу, урологу, онкологу) (3 окно регистратуры) (3 окно регистратуры),

Y1-Y3 - поток обслуженных пациентов,

Y4-Y6 - поток не обслуженных пациентов.

.2 Логическая схема работы регистратуры лечебно-профилактического центра

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

.3 Процесс функционирования СМО

Процесс функционирования данной СМО можно наглядно представить с помощью Microsoft Excel.

Пример, задания значений для расчета функционирования 1 окна регистратуры представлен в таблице 1. Время заявок задается случайной величиной исходя из условия задания: с 8.00-14.00 (что соответствует 360 мин работы 1 смены) через интервалы времени  мин, с 14.00-20.00 (что соответствует 361 мин до 720 мин работы 2 смены) . Время прихода пациента в регистратуру фиксируется в столбце таблицы - «время прихода пациента». Время начала обслуживания требования пациента рассчитывается по формуле ЕСЛИ(C3<E2;E2;C3), в столбце «время начала обсл.». Время окончания обслуживания заявки пациента рассчитывается по формуле D3+B3 и фиксируется в столбце «время окончания обслуж.». Время ожидания пациента в очереди рассчитывается по формуле D3-C3 и фиксируется в столбце «время ожидания в очереди».

Рисунок - 2.2 Алгоритм работы поликлиники регистратуры

обслуживание лечебный регистратура поликлиника

Условие обслуживания пациентов регистратуры 1 или 2 смены проверяется выражением, например, ЕСЛИ(C67<360; СЛУЧМЕЖДУ(1;9); СЛУЧМЕЖДУ(12;32)) и т.д. Условие окончания работы регистратуры проверяется выражением, ЕСЛИ(C83+A84<720; C83+A84;0) и т.д., в случае превышения времени 720 мин происходит отказ в обслуживании. Аналогичным образом были заданы параметры для 2 и 3 окон регистратуры. Пример результата работы 1 окна регистратуры представлен в таблице 2.

Таблица 1 - Пример, задания значений для расчета функционирования 1 окна регистратуры

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

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

Пример результата работы 2 окна регистратуры представлен в таблице 3.

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

Пример результата работы 3 окна регистратуры представлен в таблице 2.

Анализируя полученные результаты (таблица 2), можно сделать вывод, что: максимальная длина очереди, по сравнению с 1 и 2 окнами намного выше, т.к. время обслуживания заявок в 3 окне ниже. Первая смена регистратуры не успевает обслужить всех пациентов, за счет чего образуется очередь (в среднем в 42 пациента).

Вероятность обслуживания варьируется от 0,559 до 0,808.

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

Таблица 2 - Результата работы 3 окна регистратуры

Заключение

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

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

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

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

1. Ивницкий В.Л. Теория сетей массового обслуживания. - М: Физматлит, 2004. - 772 с.

2. Новикова Б.И, Родионов О. В., Коровин Е.Н. Моделирование биомедицинских систем, Воронеж 2008

З.Советов Б.Я.. Яковлев С.А. «Моделирование систем». [Текст] Б.Я. Советов, С.А. Яковлев. Учебное пособие 3-е юд., перераб. и доп. 2001.