Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



Рассматривается одноканальная СМО с неограниченной очередью, на которую поступает произвольный поток заявок с интенсивностью l и коэффициентом вариации n l, 0 < n l < 1. Время обслуживания также имеет произвольное распределение со средним значением и коэффициентом вариации n m, 0 < n m < 1. Для этого случая точных аналитических формул получить не удается; можно только приближенно оценить среднюю длину очереди, ограничить ее сверху и снизу.

 

L оч

 

 

Если входящий поток — простейший, то обе оценки — верхняя и нижняя — совпадают, и получается формула Полячека — Хинчина. Для грубо приближенной оценки средней длины очереди М. А. Файнбергом получена формула:

 

L оч         L сист = L оч + r

 

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

 

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

 

На вход системы из N станций поступает поток заявок с заданными (экспоненциальным или нормальным) законом распределения времени прихода, интенсивностью входного потока l и, при нормальном распределении, коэффициентом вариации n l. Каждая станция рассматривается, как одноканальная СМО с неограниченной очередью. На каждой станции задано среднее время обслуживания и, при нормальном распределении, коэффициент вариации n m. На выходе станций поток заявок может ветвиться, также может происходить отбраковка заявок. Это изменяет интенсивность входного потока на последующих станциях.

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

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

 

Глава 3

 

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

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

 

Выделим основные составные части проекта: Form1 («Задание связей между рабочими станциями») — форма для создания связей между станциями, FormTabl («Создание матрицы связей») — форма для задания коэффициентов связей, FormMultiMass («Модель многофазной многопоточной системы обслуживания») — форма для ввода входных параметров, FormRes («Результаты моделирования многофазной системы обслуживания») — форма для вывода результатов моделирования, ModStation1 — основной вычислительный модуль.

На Form1 помещены следующие компоненты: Frame — для разделения формы на несколько областей, Line и Shape — для графического отображения связей между станциями, CommandButton — для обозначения станций, реализации процедуры задания связей между станциями и перехода к другим формам.

На FormTabl помещены компоненты: Label — для обозначения названий строк и столбцов матрицы связей, TextBox — для обозначения матрицы связей и ввода коэффициентов, CommandButton — для запуска проверки правильности задания коэффициентов связей и перехода к другим формам.

На FormMultiMass помещены компоненты: Frame — для разделения формы на несколько областей, TextBox — для ввода параметров, Label — для обозначения названия вводимого параметра, OptionButton — для организации выбора типа распределения, ProgressBar — для обозначения прохождения процесса моделирования, CommandButton — для начала ввода параметров, запуска процесса моделирования, перехода к другим формам и выхода из программы.

На FormRes помещены компоненты: SSTab — для разделения формы на две страницы (графиков и числовых результатов), Frame — для разделения страницы числовых результатов на несколько областей, Label — обозначения названия выводимого показателя, PictureBox — для вывода графических результатов моделирования, TextBox — для вывода числовых результатов моделирования, CommandButton — для возвращения к формам, используемым для ввода входных параметров.

 

Алгоритм работы программы

 

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

Обобщенный алгоритм работы программы показан на рис. 2:

     


Начало

 


Ввод исходных  данных

             
 


Н              Ввод           Д

                                                                         корректен?

     
 


                                                                                                                                       

              Создание массива переходов                                                Н    Расчет по

                                                                                                                       формулам?

              Переход к первой станции                                                                        Д

         
 


    Создание входного массива на текущей станции

                                                                                                                     Расчет по имита-                    Расчет по

                                                                                                                     ционной модели                      формулам

                                 Нужна  Д

                       сортировка?

     
 


                                          Сортировка                                             Вывод рассчитанных

              Н                                                                                                  показателей

         


Создание выходного массива на текущей станции

                                                                                                                               Н     Продолжать

                                                                                                                                            работу?

                         Н     Последняя                                                      Конец

                                          станция?

        Переход к                                                                                                                      Д

        следующей               Д

          станции                                                      рис. 2


 

Программу можно поделить на две части: имитационная модель системы и расчетно-формульная модель. Для начала функционирования любой модели необходимо задать ряд входных параметров. Пользователь должен выбрать тип распределения времени прихода заявок на первую станцию (экспоненциальное — DistIndex = 0 или нормальное — DistIndex = 1) и тип распределения времени обслуживания заявок по станциям (экспоненциальное — DistIndex1 = 0 или нормальное — DistIndex1 = 1). Выбор осуществляется с помощью связанных пар компонентов OptionButton. Также пользователь задает количество рабочих станций — m (m = 1 — 10), число заявок на входе — n, среднее время между заявками во входном потоке — Ta и, при нормальном распределении на входе, стандартное отклонение (в % от среднего) — DTa (перечисленные параметры вводятся с помощью компонентов TextBox). Затем, при помощи компонентов CommandButton на форме «Задание связей между рабочими станциями», задаются связи между станциями, каждая из которых обозначаются линией, соединяющей две станции с кружком на том конце, куда связь приходит, далее, с помощью матрицы связей на форме «Создание матрицы связей», задаются весовые коэффициенты связей — pi(i). Матрица составлена из компонентов TextBox. Далее, для каждой станции, также при помощи компонентов TextBox, задается среднее время обслуживания — Ts(k), вероятность снятия заявки на выходе i-ой станции — Pr(k) и, при нормальном распределении времени обслуживания, стандартное отклонение (в % от среднего) — DTs(k).

После ввода весовых коэффициентов связей предусмотрена процедура проверки на корректность ввода. В случае некорректного задания коэффициентов, пользователю выдается сообщение об этом — MsgBox, и строка матрицы связей, в которой были заданы некорректные значения, очистится. Корректность проверяется через суммарные коэффициенты перехода: суммарный коэффициент перехода в конце каждой строки должен равняться единице. Так как коэффициенты определены типом Single, то для избежания ошибок, которые могут возникнуть в результате погрешности вычислений, производимых с переменными этого типа, проверка на равенство 1 заменяется проверкой на принадлежность интервалу (0.9999; 1.0001).

Далее, рассмотрим отдельно структуру каждой части.

 

Расчетно-формульная модель.

 

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

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

 

Имитационная модель

 

При расчете показателей с помощью имитационного моделирования вначале создается двумерный массив переходов — a1(i, k), где k — номер станции, а i — номер заявки. При создании данного массива с использованием случайных чисел, имитируются процесс прохождения заявок по станциям (на основании заданных коэффициентов переходов) и процесс отбраковки заявок (на основании заданных вероятностей снятия заявок на выходе станций). Если заявка пришла на станцию, то массиву в этой позиции присваивается значение 1; если же заявка не пришла на станцию, то массиву в данной позиции присваивается нулевое значение. Одновременно с созданием массива переходов производится расчет количества снятых заявок по станциям — NumRef(k).

Далее, для каждой станции формируется входной массив (времен прихода заявок на станцию) — a2(i, k) и выходной массив (времен выхода заявок со станции) — a3(i, k), где k — номер станции, а i — номер заявки. Входной массив первой станции образуется с использованием вспомогательной функции Rexp(T As Single) — для экспоненциального распределения (или функции Rnorm(MT As Single, DT As Single) — для нормального распределения). Выходной массив первой станции образуется из входного массива, с использованием тех же функций и функции Gener(nst As Integer). Входные массивы последующих станций образуются в соответствии с массивом переходов из выходных массивов предыдущих станций. В случае, когда заявки попадают на вход данной станции с нескольких станций (sort > 1), производится сортировка времен прихода заявок по возрастанию, с использованием вспомогательной функции Sort1(nst As Integer). После создания входного массива, на каждой последующей станции, создается выходной массив, с использованием входного массива и вспомогательных функций: Gener(nst As Integer), Rexp(T As Single) и Rnorm(MT As Single, DT As Single).

Функции Rnorm(MT As Single, DT As Single) и Rexp(T As Single) преобразуют случайную величину X, равномерно распределенную на интервале (0; 1) — Rnd, в случайную величину Y, распределенную, соответственно, по нормальному или экспоненциальному закону и предназначены для генерации нормального и экспоненциального распределения с заданными параметрами.

Функция Sort1(nst As Integer) — реализует алгоритм пирамидальной сортировки. Этот алгоритм требует операций. В нашем случае, сортируются не элементы, а индексный массив, причем таким образом, чтобы нулевые элементы исключались из сортировки (см. рис. 3).

                                         Начало

 


                                     l1 = nr(nst)/2 + 1

                                          t1=nr(nst)

     


                                                              Н                                                                                                   Н

                                                   l1 > 1?                                                                     j1 < t1?

         R1 = a2(Ind(t1), nst)         Д                                                                     Д

         
 
   


    a2(Ind(t1), nst) = a2(Ind(1), nst)                  l1 = l1 - 1       Н                 Н     a2(Ind(j1)<

                                                                                                                         j1 = t1?            a2(Ind(j1+1)?

                       t1 = t1-1                            R1 = a2(Ind(l1), nst)

                                                                                                                               Д                         Д

    Н                                                                                                                             j1 = j1 +1

                        t1 = 1?                                        j1 = l1                a2(Ind(i1), nst)=R1

 


                                 Д                                        i1 = j1                                Н     R1 > =

        a2(Ind(1), nst) = R1                                                                                     a2(Ind(j1), nst)?

                                                                                j1 = 2j1

                       Конец                                                                                                     Д

                         
 


                                                                                                            a2(Ind(i1), nst) = a2(Ind(j1), nst)

 


рис. 3

Функция Gener(nst As Integer) предназначена для генерации, с учетом нахождения заявок в очереди и простоев станции, выходного массива из входного. Она позволяет, учитывая тип распределения времени обслуживания и отбрасывая не пришедшие на станцию элементы, получить времена выхода заявок со станции(см. стр П2 приложения)

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

Результаты расчета выводятся, как численные показатели — с помощью компонентов TextBox и в виде гистограмм, с использованием компонентов PictureBox.

 

Сценарий работы программы

 

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

Количество рабочих станций — K;

Распределение времени между заявками (экспоненциальное или нормальное);

Число заявок на входе в систему — N;

Среднее время между заявками;

Стандартное отклонение [в % от среднего] —для нормального распределения.

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

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

После ввода всех необходимых параметров необходимо повторно нажать на кнопку «Ввод» для задания связей между рабочими станциями. В случае ввода количества станций превышающего предусмотренные работой программы 10, после нажатия на кнопку «Ввод» пользователю выдается сообщение об ошибке: «Количество станций не более 10 [десяти]! » и для дальнейшей работы необходимо изменить значение на корректное.

После повторного нажатия на кнопку «Ввод», на экране появляется форма «Задание связей между рабочими станциями». В левом верхнем углу данной формы расположены три кнопки: «Создать связь», «Убрать связь» и «Загрузить связи». В зависимости от количества рабочих станций, заданного пользователем в общих параметрах, на форме расположены от 1 до 10 рабочих станций. Каждая станция представлена в виде двух кнопок (левой и правой), вплотную прилегающих друг к другу. Левая кнопка станции обозначена «S» (Station), а правая показывает номер данной рабочей станции (от 1 до 10). Для задания связей между станциями нужно:

Нажать на кнопку «Создать связь»;

(далее вводятся все необходимые связи)

Нажать на правую кнопку (с указанием номера) той станции, откуда пойдет связь;

Нажать на левую кнопку (с обозначением «S» ) той станции, куда пойдет связь.

Чтобы убрать связь между станциями, нужно:

Нажать на кнопку «Убрать связь»;

(далее удаляются все необходимые связи)

Нажать на правую кнопку (с указанием номера) той станции, откуда идет связь;

Нажать на левую кнопку (с обозначением «S» ) той станции, куда идет связь.

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

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

Чтобы ввести связи, нужно нажать на кнопку «Загрузить связи».

После нажатия на кнопку «Загрузить связи», на экране появляется форма «Создание матрицы связей». Эта форма представляет собой матрицу коэффициентов связи между станциями. В зависимости от того, какие связи задал пользователь в форме «Задание связей между рабочими станциями», становятся активными соответствующие этим связям поля матрицы (окна для ввода значений коэффициентов связи). Строки матрицы пронумерованы от 1 до 9, столбцы пронумерованы от 2 до 10. Строка обозначает ту станцию, откуда идет связь, столбец — ту станцию, куда связь приходит. В активные окна пользователь должен внести значения коэффициентов связей, соответствующих вероятностям того, что заявка пойдет именно по данному каналу связи. Внизу этой формы расположены три кнопки: «Возврат», «Проверить» и «Загрузить». После того, как пользователь задал значения всех коэффициентов, он должен нажать на кнопку «Проверить» для проверки корректности введенных значений. Так как сумма вероятностей выхода заявки со станции по всем каналам должна быть равна единице, то по каждой станции проводится проверка выполнения этого условия и значение приводится к корректному (вероятность последней, задаваемой по строке связи, считается как единица минус сумма вероятностей всех предыдущих связей по этой строке). Если сумма вероятностей всех связей, кроме последней больше единицы, то пользователю выдается сообщение «Суммарная вероятность не может быть больше единицы! » и все окна этой строки очистятся, после чего пользователь должен заново задать эти значения и повторить проверку корректности. После проверки корректности нужно загрузить значения коэффициентов, нажав на кнопку «Загрузить». Кнопка «Возврат» позволяет вернуться в форму «Задание связей между рабочими станциями».

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

Распределение времени обслуживания для всех станций (экспоненциальное или нормальное);

Среднее время обслуживания для каждой станции;

Вероятность снятия заявки на выходе i-ой станции;

Стандартное отклонение [в % от среднего] —для нормального распределения.

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

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

После нажатия на кнопку «Старт» или на кнопку «По формулам» происходит моделирование и на экране появляется форма «Результаты моделирования многофазной системы обслуживания». Эта форма состоит из двух частей (представленные на двух страницах): «Графики» и «Числовые результаты». Для выбора страницы в верхней части формы помещены две закладки «Графики» и «Числовые результаты», при нажатии на которые пользователь сможет ознакомиться соответственно с графическими или числовыми результатами.

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

Среднее время ожидания;

Среднее время простоя;

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

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

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

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

Параметры при расчете по формулам включают:

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

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

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

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

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

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

При нажатии на закладку «Числовые результаты», на экране появятся числовые результаты моделирования. При имитационном моделировании они включают для каждой станции:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Интерфейс программы

 

Далее представлены примеры интерфейса программы.

Глава 4

 

Исследование модели

 

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


Поделиться:



Последнее изменение этой страницы: 2019-10-03; Просмотров: 176; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.129 с.)
Главная | Случайная страница | Обратная связь