Разработка и исследование имитационной модели разветвленной СМО (системы массового обслуживания) в среде VB5

Разработка и исследование имитационной модели разветвленной СМО (системы массового обслуживания) в среде VB5

Аннотация к работе «Разработка и исследование имитационной

модели разветвленной СМО (системы массового обслуживания)

в среде VB5»

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

прохождения потока заявок (закон распределения времени между поступлением

заявок экспоненциальный или нормальный) по рабочим станциям (одноканальным

СМО с неограниченной очередью; закон распределения времен обслуживания

экспоненциальный или нормальный; максимальное число рабочих станций 10), с

возможностью ветвления, объединения потоков и отбраковки заявок. Программа

позволяет на основании результатов моделирования рассчитывать основные

характеристики СМО, а также рассчитывать некоторые средние показатели СМО

по формулам. Для создания программы выбрана среда программирования Visual

Basic 5.

Исследование модели включает проведение с помощью программы ряда

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

основании имитационного моделирования, с результатами расчета по формулам.

Цель исследования — сделать выводы о возможности применения приближенных

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

Содержание.

Глава 1 Введение 6

Глава 2 Математическое описание модели 11

Глава 3 Создание программы 27

Глава 4 Исследование модели 46

Глава 5 Экономическая часть 63

Глава 6 Охрана труда 81

Глава 7 Заключение 87

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

Приложение

Глава 1

Введение

1.1 Актуальность разработки и перспективы применения программы

В современном мире существенно повысилась доступность компьютерной

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

производственных областях. В связи с этим выросла аудитория потенциальных

потребителей компьютерных программ и следовательно увеличилась

целесообразность их создания.

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

систем, называемых системами массового обслуживания (СМО). Примерами таких

систем могут служить: телефонные станции, ремонтные мастерские, билетные

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

этих систем состоит из какого-то числа обслуживающих единиц (каналов

обслуживания) Такими каналами могут быть: линии связи, рабочие точки,

кассиры, продавцы, лифты, автомашины и др.

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

«требований»), поступающих в какие-то случайные моменты времени.

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

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

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

времени на входе СМО скапливается излишне большое число заявок (они либо

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

периоды СМО будет работать с недогрузкой или вообще простаивать.

Последовательная линейная структура СМО характерна, например, для

поточных (автоматических и неавтоматических) линий конвейерного типа.

Различие во времени обработки деталей на таких линиях связано, в основном,

с процессами «отказа» и «восстановления».

Гибкая производственная система (ГПС) — это система с высокой степенью

автоматизации, предназначенная для изготовления деталей различных видов,

выпускаемых малыми и средними партиями. Она включает группу станков с

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

систему загрузки и разгрузки заготовок и конвейерную систему

транспортирования заготовок от одной операции до следующей, электронно-

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

управления всем объемом работ, составляющую математическое обеспечение

автоматизированного комплекса.

Если рассматривать структуру гибких производственных систем, то для них

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

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

и использовать различные маршруты обработки. ГПС, в отличие от поточных

линий, необходимо рассматривать уже не как линейную и последовательную, а

как сложную разветвленную структуру. Как в ГПС, так и в поточных линиях

необходимо также предусмотреть возможность отбраковки обрабатываемых

деталей на различных стадиях обработки.

Данная программа дает возможность смоделировать как линейную, так и

разветвленную структуру. Программа может использоваться для оптимизации

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

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

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

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

«слабые» места в системе или осознать необходимость введения в нее каких-

либо дополнительных элементов. Далее можно, меняя различные параметры в

программе, достигать оптимального соотношения простоев и очередей.

Оптимизация процесса обслуживания способна существенно повысить

эффективность работы предприятия.

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

разрабатываемой программы.

1.2 Постановка задачи (обобщенное описание модели).

На вход системы из N станций поступает поток заявок с заданным законом

распределения времени прихода (экспоненциальным или нормальным). Задаются

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

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

станциях (экспоненциальный или нормальный), параметры распределения и

вероятности отбраковки заявок по станциям. Предусмотрены два варианта

расчета показателей — с помощью имитационной модели и по формулам.

1. При имитационном моделировании для каждой станции рассчитываются:

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

1.2 Среднее время простоя станции;

1.3 Максимальная длина очереди;

1.4 Число снятых заявок;

1.5 Коэффициент использования;

1.6 Среднее время нахождения заявки на станции;

1.7 Максимальное время нахождения заявки на станции.

Также выводятся общие показатели системы:

1.8 Общее время прихода N заявок;

1.9 Время выхода последней заявки;

1.10 Общий коэффициент использования системы по времени;

1.11 Общий коэффициент использования системы по числу заявок.

2. При расчете по формулам для каждой станции рассчитываются:

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

2.2 Среднее время простоя станции;

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

2.4 Среднее время нахождения заявки на станции;

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

корректные результаты и интересующие показатели можно рассчитывать только с

помощью имитационной модели.

1.3 Обоснование выбора среды программирования Visual Basic 5

Начиная изучать что-то новое, полезно посмотреть и в недалекое прошлое.

Особенно это касается программирования, которое в последние десять лет

развивается просто фантастическими темпами .

Очень давно, лет тридцать назад, произошел массовый переход от машинных

кодов к языкам программирования (типа Algol, Cobol, PL/1) и широкому

использованию методов структурного программирования. Программы стали

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

подпрограмм, облегчающие многие задачи, но все равно программистам хватало

трудностей, особенно при разработке пользовательского интерфейса.

В конце 80-х—начале 90-х годов появились системы, где применялось

объектно-ориентированное программирование, в частности, языки Object

Pascal, C++ и др. Программы стали строиться не из больших по размеру

процедур и функций, перерабатывающих сложные структуры данных, а из

сравнительно простых кирпичиков -объектов, в которых находились данные и

подпрограммы их обработки. Гибкость объектов позволила просто

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

Программисты обзавелись готовыми библиотеками объектов, но, как и раньше,

интерфейс каждый делал по-своему.

В начале 90-х годов началось широкое распространение графического

пользовательского интерфейса, который с появлением операционной системы

Windows 3.1 и особенно Windows 95 был практически стандартизирован.

Несмотря на критику, эти системы завоевали мир, и Windows-стандартам

осталось только подчиняться. Однако соблюдать новые стандарты интерфейса

при разработке собственных программ оказалось совсем не легко, так как для

этого не было хороших средств. Разработка приложений для Windows была

уделом избранных, поэтому первые годы Windows стали для программистов

сложным испытанием.

В 1993 году появилась первая система визуального программирования

Visual Basic. Она стала незаменимой для всех, желающих быстро создавать

Windows-приложения. Строительными блоками программы стали

компоненты—объекты, имеющие визуальное представление на стадии

проектирования и во время работы. Проектирование пользовательского

интерфейса упростилось на порядок.

В 1995 году фирма Borland выпустила среду Delphi, которая позволила

программистам создавать собственные компоненты и строить из них

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

компонентов. В 1997 году появилась среда C++Builder — полный аналог Delphi,

в котором используется язык C++ (вместо Object Pascal).

В дальнейшем появлялись новые усовершенствованные версии Delphi,

C++Builder и Visual Basic, предоставляющие пользователям дополнительные

возможности.

Сегодня компьютерный мир переживает революцию Internet, которая в

первую очередь является революцией в сфере информационных услуг. Internet

повлиял и на технологию программирования, подарив миру мобильный

интерпретируемый язык Java. Новый язык позволил создавать графические

приложения, работающие на любых платформах, будь то Windows, OS/2, Unix и

др. Однако технология Java находится в развитии и еще не устоялась, чтобы

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

пока лучше использовать хорошо проверенные Delphi, C++Builder и Visual

Basic. Кстати, эти системы содержат и компоненты для доступа к Internet.

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

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

достаточно короткий срок. Сотни гениальных программ канули в Лету только

потому, что устарели уже на стадии реализации. Особенно остро эта проблема

стоит сейчас, когда одна фирма дышит в затылок другой, причем производят

они очень похожие продукты. Одних текстовых редакторов десятки, не говоря

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

которой быстрее всего можно реализовать проект, это среда Visual Basic.

Глава 2

Математическое описание модели.

Данный раздел описания базируется на работах Е. С. Вентцель.

2.1 Марковские случайные процессы.

Случайный процесс, протекающий в системе, называется марковским, если

для любого момента времени t0 вероятностные характеристики процесса в

будущем зависят только от его состояния в данный момент t0 и не зависят от

того, когда и как система пришла в это состояние

Пусть в момент t0 система находится в определенном состоянии S0. Мы

наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю

предысторию процесса, все, что было при t < t0. Нас интересует будущее (t >

t0). В точности невозможно его предугадать, так как процесс — случайный, а

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

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

время ( система S окажется в состоянии S1 или сохранит состояние S0, и т.

п.

Для марковского случайного процесса такое «вероятностное предсказание»

оказывается гораздо проще, чем для немарковского. Если процесс —

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

системы S0 и забыв о его «предыстории» (поведении системы при t < t0). Само

состояние S0, разумеется, зависит от прошлого, но как только оно

достигнуто, о прошлом можно забыть. В марковском процессе «будущее зависит

от прошлого только через настоящее».

На практике часто встречаются процессы, которые если не в точности

марковские, то могут быть в каком-то приближении рассмотрены как

марковские. Пример: система S — группа самолетов, участвующих в воздушном

бою. Состояние системы характеризуется числом самолетов «красных» — x и

«синих» — y, сохранившихся (не сбитых) к определенному моменту. В момент t0

нам известны численности сторон — x0 и y0. Нас интересует вероятность того,

что в момент времени t0 + ( численный перевес будет на стороне «красных». В

первую очередь эта вероятность будет зависеть от того, в каком состоянии

находится система в момент t0, а не от того, когда и в какой

последовательности погибали сбитые до момента t0 самолеты.

В сущности, любой процесс можно рассматривать как марковский, если все

параметры из «прошлого», от которых зависит «будущее», включить в

«настоящее». Например, пусть речь идет о работе некоторого технического

устройства; в момент t0 оно еще исправно, и нас интересует вероятность

того, что оно проработает еще время (. Если за настоящее состояние системы

считать просто «система исправна», то процесс безусловно немарковский,

потому что вероятность того, что она не откажет за время (, зависит, в

общем случае, от того, сколько времени она уже проработала и когда был

последний ремонт. Если оба эти параметра (общее время работы и время после

последнего ремонта) включить в настоящее состояние системы, то процесс

можно будет считать марковским. Однако такое «обогащение настоящего за счет

предыстории» далеко не всегда бывает полезно, поэтому в дальнейшем, говоря

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

параметров, определяющих «настоящее».

На практике марковские процессы в чистом виде обычно не встречаются, но

нередко приходится иметь дело с процессами, для которых влиянием

«предыстории» можно пренебречь. При изучении таких процессов можно с

успехом применять марковские модели.

В исследовании операций большое значение имеют так называемые

марковские случайные процессы с дискретными состояниями и непрерывным

временем. Процесс называется процессом с дискретными состояниями, если его

возможные состояния S1, S2, S3, ... можно заранее перечислить

(перенумеровать), и переход системы из состояния в состояние происходит

«скачком», практически мгновенно. Процесс называется процессом с

непрерывным временем, если моменты возможных переходов из состояния в

состояние не фиксированы заранее, а неопределенны, случайны, т. е. если

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

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

схемой — так называемым графом состояний. Состояния системы изображаются

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

состояния в состояние — стрелками, соединяющими состояния. Мы будем

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

состояний: S1, S2, ..., Sn.

Потоком событий называется последовательность однородных событий,

следующих одно за другим в случайные моменты времени. Например: поток

вызовов на телефонной станции; поток отказов (сбоев) ЭВМ; поток

железнодорожных составов, поступающих на сортировочную станцию, и т. д.

Важной характеристикой потока событий является его интенсивность ( —

среднее число событий, приходящееся на единицу времени. Интенсивность

потока может быть как постоянной ((= const), так и переменной, зависящей от

времени t. Например, поток автомашин, движущихся по улице, днем

интенсивнее, чем ночью, в часы пик — интенсивнее, чем в другие часы.

Поток событий называется регулярным, если события следуют одно за

другим через определенные, равные промежутки времени. На практике чаще

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

Поток событий называется стационарным, если его вероятностные

характеристики не зависят от времени. Поток событий называется потоком без

последействия, если для любых двух непересекающихся интервалов времени t1 и

t2 число событий, попадающих на один из них, не зависит от того, сколько

событий попало на другой. По сути это означает, что события, образующие

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

причем каждое вызвано своими собственными причинами.

Поток событий называется ординарным, если события в нем появляются

поодиночке, а не группами по несколько сразу. Например, поток клиентов,

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

нельзя сказать о потоке клиентов, направляющихся в загс для регистрации

брака. Поток поездов, подходящих к станции, ординарен, а поток вагонов —

неординарен. Если поток событий ординарен, то вероятностью попадания на

малый интервал времени t двух или более событий можно пренебречь.

Поток событий называется простейшим (или стационарным пуассоновским),

если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет

последействия. Название «простейший» связано с тем, что процессы, связанные

с простейшими потоками, имеют наиболее простое математическое описание.

Самый простой, на первый взгляд, регулярный поток не является «простейшим»,

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

связаны жесткой функциональной зависимостью.

Простейший поток играет среди других потоков особую роль. А именно, при

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

стационарных и ординарных потоков (сравнимых между собой по интенсивности)

получается поток, близкий к простейшему.

Для простейшего потока с интенсивностью ( интервал между соседними

событиями имеет так называемое экспоненциальное распределение с плотностью

[pic] (t > 0) (1)

Величина ( в формуле (1) называется параметром показательного закона.

Для случайной величины Т, имеющей экспоненциальное распределение,

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

квадратическое отклонение (T равно математическому ожиданию:

[pic] (2)

В теории вероятностей в качестве «меры случайности» неотрицательной

случайной величины нередко рассматривают так называемый коэффициент

вариации:

[pic] (3)

Из формул (2), (3) следует, что для показательного распределения (t =

1, т. е. для простейшего потока событий коэффициент вариации интервалов

между событиями равен единице.

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

событиями вообще не случаен ((t = 0), коэффициент вариации равен нулю.

Элементом вероятности называется вероятность попадания на этот интервал

хотя бы одного события потока. Легко доказать, что элемент вероятности (с

точностью до малых величин более высокого порядка по сравнению с (t) равен:

[pic] (4)

т. е. для простейшего потока элемент вероятности равен интенсивности

потока, умноженной на длину элементарного интервала. Элемент вероятности, в

силу отсутствия последействия, совершенно не зависит от того, сколько

событий и когда появлялись ранее.

Нормальное распределение занимает центральное место среди непрерывных

распределений. Его плотность определяется формулой:

F(t) = [pic] (5)

где ( > 0, m — параметры распределения. При ( = 1 и m = 0 имеет место

стандартное нормальное распределение с плотностью:

F(t) = [pic] (6)

Пусть рассматривается система S, имеющая n возможных состояний S1, S2,

..., Sn. Назовем вероятностью i-го состояния вероятность pi(t) того, что в

момент t система будет находиться в состоянии Si. Очевидно, что для любого

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

Имея в своем распоряжении размеченный граф состояний, можно найти все

вероятности состояний pi(t) как функции времени. Для этого составляются и

решаются так называемые уравнения Колмогорова — дифференциальные уравнения

особого вида, в которых неизвестными функциями являются вероятности

состояний.

Что будет происходить с вероятностями состояний при t ( ( ? Будут ли

p1(t), p2(t),... стремиться к каким-то пределам? Если эти пределы

существуют и не зависят от начального состояния системы, то они называются

финальными вероятностями состояний. В теории случайных процессов

доказывается, что если число n состояний системы конечно и из каждого из

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

вероятности существуют.

Финальную вероятность состояния Si можно истолковать как среднее

относительное время пребывания системы в этом состоянии.

Граф состояний для схемы гибели и размножения имеет вид, показанный на

рис. 1. Особенность этого графа в том, что все состояния системы можно

вытянуть в цепочку, в которой каждое из средних состояний связано прямой и

обратной стрелкой с каждым из соседних состояний — правым и левым, а

крайние состояния — только с одним соседним состоянием. Термин «схема

гибели и размножения» ведет начало от биологических задач, где подобной

схемой описывается изменение численности популяции.

Схема гибели и размножения

(01 (12 (23 (k-

1,k (k,k+1 (n-1,n

| | | | | | | | | | | | | | | |

|S0 | |S1 | |S2 | |...| |Sk | |...| |Sn-1 | |Sn |

| | | | | | | | | | | | | | | |

| | | | | | |...| | | |...| | | | |

| | | | | | | | | | | | | | | |

| | | | | | |ю | | | | | | | | |

(10 (21 (32 (k,k-

1 (k+1,k (n,n-1

[pic][pic][pic] [pic]

( — интенсивность потока; p0, pk — финальные вероятности состояний

Формулы Литтла

[pic] Lсист — среднее число заявок в системе;

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

Wоч[pic]L оч Lоч — среднее число заявок в очереди;

Wоч — среднее время пребывания заявки в очереди

( — интенсивность потока обслуживаний; ( — интенсивность потока заявок

( /( = ( (приведенная интенсивность потока заявок)

( — среднее число заявок, приходящее за среднее время обслуживания одной

заявки

рис. 1

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

При исследовании операций часто приходится сталкиваться с работой

систем массового обслуживания. СМО могут быть одноканальными и

многоканальными.

Процесс работы СМО представляет собой случайный процесс с дискретными

состояниями и непрерывным временем; состояние СМО меняется скачком в

моменты появления каких-то событий (прихода новой заявки, окончания

обслуживания, момента, когда заявка, которой «надоело ждать», покидает

очередь).

Предмет теории массового обслуживания — построение математических

моделей, связывающих заданные условия работы СМО (число каналов, их

производительность, правила работы, характер потока заявок) с интересующими

нас характеристиками — показателями эффективности СМО, описывающими, с той

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

качестве таких показателей (в зависимости от обстановки и целей

исследования) могут применяться разные величины, например: среднее число

заявок, обслуживаемых СМО в единицу времени; среднее число занятых каналов;

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

вероятность того, что число заявок в очереди превысит какое-то значение,

простои, и т. д.

Математический анализ работы СМО очень упрощается, если процесс этой

работы — марковский. Для этого достаточно, чтобы все потоки событий,

переводящие систему из состояния в состояние (потоки заявок, «потоки

обслуживания»), были простейшими. Если это свойство нарушается, то

математическое описание процесса становится гораздо сложнее и довести его

до явных, аналитических формул удается лишь в редких случаях. Однако

аппарат простейшей, марковской теории массового обслуживания может

пригодиться для приближенного описания работы СМО даже в тех ситуациях,

когда потоки событий — не простейшие. Во многих случаях для принятия

разумного решения по организации работы СМО вовсе и не требуется точного

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

ориентировочного.

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

признаков. Первое деление: СМО с отказами и СМО с очередью. В СМО с

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

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

Примеры СМО с отказами встречаются в телефонии: заявка на разговор,

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

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

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

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

значение) СМО с очередью; недаром теория массового обслуживания имеет

второе название: «теория очередей».

СМО с очередью подразделяются на разные виды, в зависимости от того,

как организована очередь — ограничена она или не ограничена. Ограничения

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

«СМО с нетерпеливыми заявками»). При анализе СМО должна учитываться также и

«дисциплина обслуживания» — заявки могут обслуживаться либо в порядке

поступления (раньше пришла, раньше обслуживается), либо в случайном

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

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

абсолютным — когда заявка с более высоким приоритетом «вытесняет» из-под

обслуживания заявку с низшим, так и относительным — когда начатое

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

лишь право на лучшее место в очереди.

Существуют СМО с так называемым многофазовым обслуживанием, состоящим

из нескольких последовательных этапов или «фаз» (например, покупатель,

пришедший в магазин, должен сначала выбрать товар, затем оплатить его в

кассе, после чего получить на контроле).

Кроме этих признаков, СМО делятся на два класса: «открытые» и

«замкнутые». В открытой СМО характеристики потока заявок не зависят от

того, в каком состоянии находится сама СМО (сколько каналов занято). В

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

станков, время от времени требующих наладки, то интенсивность потока

«требований» со стороны станков зависит от того, сколько их уже неисправно

и ждет наладки. Это — пример замкнутой СМО.

Рассмотрим вывод упомянутой ранее формулы Литтла, связывающей (для

предельного, стационарного режима) среднее число заявок Lсист, находящихся

в системе массового обслуживания (т. е. обслуживаемых или стоящих в

очереди), и среднее время пребывания заявки в системе Wсист.

Рассмотрим любую СМО (одноканальную, многоканальную, марковскую,

немарковскую, с неограниченной или с ограниченной очередью) и связанные с

нею два потока событий: поток заявок, прибывающих в СМО, и поток заявок,

покидающих СМО. Если в системе установился предельный, стационарный режим,

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

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

интенсивность (.

Обозначим: X(t)—число заявок, прибывших в СМО до момента t, Y(t) —

число заявок, покинувших СМО до момента t. И та, и другая функции являются

случайными и меняются скачком (увеличиваются на единицу) в моменты приходов

заявок (X(t)) и уходов заявок (Y(t)). Для любого момента t их разность Z(t)

= X(t) - Y(t) — это число заявок, находящихся в СМО.

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

среднее число заявок, находящихся в СМО. Оно будет равно интегралу от

функции Z(t) на этом промежутке, деленному на длину интервала T:

[pic] (7)

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

X(t) и Y(t). Фигура состоит из прямоугольников, каждый из которых имеет

высоту, равную единице, и основание, равное времени пребывания в системе

соответствующей заявки (первой, второй и т. д.). Обозначим эти времена как

t1, t2,... Правда, под конец промежутка Т некоторые прямоугольники войдут в

эту фигуру не полностью, а частично, но при достаточно большом Т этим можно

пренебречь. Таким образом, можно считать, что

[pic], (8)

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

Разделим правую и левую часть (8) на длину интервала Т. Получим, с

учетом (7):

[pic] (9)

Разделим и умножим правую часть (9) на интенсивность (:

[pic] (10)

Величина T( — это среднее число заявок, пришедших за время Т. Если мы

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

время пребывания заявки в системе Wсист- Итак,

[pic] (11)

Это и есть формула Литтла: для любой СМО, при любом характере потока

заявок, при любом распределении времени обслуживания, при любой дисциплине

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

заявок в системе, деленному на интенсивность потока заявок.

Точно таким же образом выводится вторая формула Литтла, связывающая

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

очереди Lоч.

Lоч = ( Wоч

2.3 Варианты систем массового обслуживания

1. n-канальная СМО с отказами

A — абсолютная пропускная способность (среднее число заявок,

обслуживаемых в единицу времени);

Q — относительная пропускная способность (средняя доля пришедших

заявок, обслуживаемых системой);

Pотк — вероятность того, что заявка покинет СМО необслуженной;

[pic] — среднее число занятых каналов; [pic];

[pic]; [pic];

[pic] ; [pic];

[pic]; [pic]

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

Pзан — вероятность того, что канал занят; Lоб — среднее число заявок

под обслуживанием

[pic]; [pic];

[pic];

[pic];

[pic]; [pic] ;

[pic] ; [pic]Lоч[pic] ;

Wоч[pic]

3. Одноканальная СМО с неограниченной очередью, простейшим потоком

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

На одноканальную СМО поступает простейший поток заявок с интенсивностью

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

ожиданием [pic] и коэффициентом вариации ((. (( — отношение среднего

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

ожиданию.

Формулы Полячека — Хинчина:

Lоч[pic] ; Lсист[pic]

Далее, согласно формуле Литтла:

Wоч[pic] ; Wсист[pic]

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

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

Рассматривается одноканальная СМО с неограниченной очередью, на которую

поступает произвольный поток заявок с интенсивностью ( и коэффициентом

вариации ((, 0 < (( < 1. Время обслуживания также имеет произвольное

распределение со средним значением [pic] и коэффициентом вариации ((, 0 <

(( < 1. Для этого случая точных аналитических формул получить не удается;

можно только приближенно оценить среднюю длину очереди, ограничить ее

сверху и снизу.

[pic]Lоч[pic]

[pic][pic]

Если входящий поток — простейший, то обе оценки — верхняя и нижняя —

совпадают, и получается формула Полячека — Хинчина. Для грубо приближенной

оценки средней длины очереди М. А. Файнбергом получена формула:

Lоч [pic][pic] Lсист = Lоч + (

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

через Lоч и Lсист по формуле Литтла делением на (

2.4 Математическое описание разрабатываемой модели.

На вход системы из N станций поступает поток заявок с заданными

(экспоненциальным или нормальным) законом распределения времени прихода,

интенсивностью входного потока ( и, при нормальном распределении,

коэффициентом вариации ((. Каждая станция рассматривается, как

одноканальная СМО с неограниченной очередью. На каждой станции задано

среднее время обслуживания [pic] и, при нормальном распределении,

коэффициент вариации ((. На выходе станций поток заявок может ветвиться,

также может происходить отбраковка заявок. Это изменяет интенсивность

входного потока на последующих станциях.

При имитационном моделировании поэтапно имитируется (с использованием

генератора случайных чисел) весь описанный процесс: моделируются входной

поток и потоки обслуживаний, имитируются процессы ветвления и объединения

потоков, а также процесс отбраковки заявок.

Расчетно-формульная модель такой системы может рассматриваться только в

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

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

всех станций выполняется условие ([pic])

Глава 3

Создание программы

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

Страницы: 1, 2, 3