Теоретические сведения

Системы массового обслуживания представляют собой класс математических схем (Q – схем), применяемых для формализации процессов функционирования системы, которые по своей сути являются процессами обслуживания [13].

Формализацию реальной системы с помощью Q – схемы рассмотрим на конкретном примере.

Пример 1. Моделируется работа производственного участка, изготавливающего детали определенного вида. Процесс изготовления детали требует последовательного выполнения двух операций соответственно на токарном и фрезерном станках. На участке имеется 2 токарных станка и 1 фрезерный. Известно, что поток заказов на изготовление деталей пуассоновский с интенсивностью λ=0.05 (деталей в минуту). Допустимая очередь заказов на изготовление деталей перед токарным станком равна 5. Если очередь равна 5-ти, то очередной заказ передается на другой производственный участок. Допустимая очередь заказов перед фрезерным станком равна 2. Если в очереди 2 заказа, то очередной заказ не принимается токарными станками, пока не появится место в очереди. Время обработки на токарных станках в среднем: =15 минут (1-ый станок); =20 минут (2-ой станок), на фрезерном станке в среднем: =5 минут (закон распределения показательный). Требуется определить показатели эффективности функционирования системы.

На рис. 1 приведена структура Q – схемы производственного участка. В качестве элементов Q – схемы рассматриваются элементы трех типов: И – источники заявок; Н – накопители; К – каналы обслуживания заявок. Кроме связей, отражающих движение заявок в Q – схеме (сплошные линии), также могут быть различные управляющие связи. Например, блокировки обслуживающих каналов (по входу и по выходу): «клапаны» изображены в виде треугольников, а управляющие связи – пунктирные линии. Блокировка канала по входу означает, что этот канал отключается от входящего потока заявок, а блокировка канала по выходу указывает, что заявка, уже обслуженная блокированным каналом, остается в этом канале до момента снятия блокировки (открытия «клапана»). В этом случае, если перед накопителем нет «клапана», при его переполнении будут иметь место потери заявок. Помимо выходящего потока обслуженных заявок можно говорить также о потоке потерянных заявок. На рис. 1 изображена многоканальная (параллельное соединение каналов) и многофазная (последовательное соединение каналов и их параллельных композиций) Q – схема.

Рис. 1.

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

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

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

H – множество собственных параметров СМО (количество фаз обслуживания заявки; количество накопителей и каналов на каждой фазе, емкости накопителей);

Z – множество состояний системы (например, Z₀ – в СМО нет заявок; Z₁ – в СМО одна заявка, которая обслуживается каналом; Z₂ – в СМО две заявки: одна обслуживается, другая стоит в очереди на обработку и занято одно место в накопителе заявок и т.д.);

R – оператор сопряжения или структурная схема СМО (рис. 1);

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

Для оценки показателей эффективности функционирования СМО можно использовать как аналитический аппарат, разработанный в теории массового обслуживания [4,6,7], так и методы имитационного моделирования [3,4,9-12,15-16].

Теоретические сведения для расчета СМО аналитическим методом приведены в [4, пп. 2.1.,2.2.]. Аналитический метод используется для решения только узкого класса задач, когда выполняется следующее условие: все потоки, переводящие систему из состояния в состояние, простейшие пуассоновские, т.е. в системе протекает марковский случайный процесс [6,14].

На практике функционирование значительной части систем может описываться в рамках марковского случайного процесса «гибели и размножения» [6,14]. Термин ведет начало от биологических задач, процесс описывает изменение численности популяции. Переход из состояния в состояние происходит в момент гибели (окончания обслуживания заявки) или рождения особи (прихода заявки).

Выделяют три основных типа СМО, соответствующих схеме «гибели и размножения» [4, п. 2.2.2]: 1 тип – многоканальные (одноканальные) системы без потерь с неограниченным ожиданием и бесконечным потоком требований на входе (разомкнутые системы); 2 тип – многоканальные (одноканальные) системы с отказами и бесконечным потоком требований на входе (разомкнутые системы); 3 тип – многоканальные (одноканальные) системы без потерь с источником конечного числа требований (замкнутые системы). Для каждого из этих типов выведены формулы для расчета вероятностей состояний и оценки показателей эффективности функционирования СМО [4, п. 2.2.3]. В этом случае применение аналитического метода сводится к построению размеченного графа состояний СМО, выбору типа СМО и основных расчетных формул, проведению расчетов и анализу полученных результатов. Приведем примеры построения размеченного графа состояний системы.

Пример 2. В вычислительную систему на обработку поступают задания в среднем через =2 минуты. Задания обрабатываются одним из 3-х компьютеров. Время обработки для всех компьютеров одинаковое и составляет в среднем: =6 минут. Все потоки, протекающие в системе, простейшие пуассоновские. Для этой системы размеченный граф состояний имеет вид:

Рис. 2.

λ=1/ =0.5 – интенсивность входного потока заявок;

μ=1/ =1/6 – интенсивность потока обслуживания;

S₀ – в системе нет заявок;

S₁ – в системе одна заявка, которая обрабатывается компьютером;

S₂ – в системе две заявки, которые обрабатывается компьютерами;

S₃ – две заявки обрабатываются, одна стоит в очереди на обработку.

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

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

Рис. 3.

S₄ – две заявки обрабатываются, две стоят в очереди на обработку.

Система относится ко второму типу, граф состояний конечен.

Пример 4. На обработку к серверному компьютеру принимаются задания от трех компьютеров – терминалов. Новое задание компьютером – терминалом не генерируется, пока не закончена обработка предыдущего задания. Все потоки, протекающие в системе, простейшие пуассоновские. Средний интервал между поступлениями заданий: =6 секунд; среднее время обработки задания: =2 секунды. Для этой системы размеченный граф состояний имеет вид:

Рис. 4.

Система замкнутая, относится к третьему типу.

Имитационное моделирование в среде GPSS/World процесса функционирования систем массового обслуживания первых двух типов приведено в [3]. Рассмотрим реализацию в GPSS/World системы, описанной в примере 4 (система третьего типа, замкнутая):

; SEGMENT 1 INITIAL X1,1 GENERATE ,,,3 MET1 ADVANCE(EXPONENTIAL(1,0,6)) QUEUE B SEIZE COMP ADVANCE(EXPONENTIAL(2,0,2)) DEPART B RELEASE COMP SAVEVALUE 1+,1 SAVEVALUE X1,QT$B TRANSFER ,MET1 ; SEGMENT 2 GENERATE 6000 TERMINATE 1 START 1 ; SEGMENT 3 GENERATE 1 TEST E Q$B,0,MET2 SAVEVALUE PP0+,(1/6000) MET2 TEST E Q$B,1,MET3 SAVEVALUE PP1+,(1/6000) MET3 TEST E Q$B,2,MET4 SAVEVALUE PP2+,(1/6000) MET4 TEST E Q$B,3,MET5 SAVEVALUE PP3+,(1/6000) MET5 TERMINATE

; Начальное значение номера ; Определение кол-ва компьютеров ; Генерация задания ; Постановка в очередь ; Занятие сервера ; Обработка сервером ; Выход из очереди ; Освобождение сервера ; Вывод времени пребывания ; задания в системе ; Переход к генерации следующего ; задания ; Моделирование 100 минут работы ; Завершение работы ; Начало прогона модели ; Генерация вспомогательного ; потока заявок для сбора ; статистики

В программе для генерации входного пуассоновского потока заданий используется библиотечная процедура экспоненциального распределения с λ=1/ =1/6 и генератором случайных чисел RN1:

EXPONENTIAL(1,0,6)

Для генерации пуассоновского потока обработки заданий применяется аналогичная процедура с μ=1/ =1/2 и генератором случайных чисел RN2.

Для вывода в файл отчета GPSS последовательности времен пребывания задания в системе используются блоки SAVEVALUE. Блок SAVEVALUE позволяет присвоить значение величине. Формат блока:

SAVEVALUE A[+,-],B

В поле А задается имя сохраняемой величины, в поле В – присваиваемое значение. Если используется режим увеличения [+] или уменьшения [-], то предыдущее значение сохраняемой величины соответственно увеличивается или уменьшается на значение В.

В третьем сегменте модели вычисляются вероятности пребывания в системе 0,1,2 и 3-х заявок. Для этого формируется вспомогательный поток заявок. Каждую секунду генерируется заявка, проверяется текущее количество заявок в системе (Q$B) и увеличивается соответствующий счетчик.

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

GPSS World Simulation Report – Ex1

Monday, May 07, 2007 18:56:05

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 6000.000 22 1 0

…

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

COMP 1917 0.659 2.063 1 1 0 0 0 1

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

B 3 2 1918 0 1.055 3.302 3.302 0

SAVEVALUE VALUE

1 1917

2 0.566

3 1.472

4 1.697

5 1.599

6 1.309

7 1.686

8 2.617

9 2.685

…

PP0 0.341

PP1 0.346

PP2 0.228

PP3 0.084

Время моделирования системы составило 6000 секунд (100 минут). За это время было обработано 1917 заявок. Среднее время пребывания задания в системе: 3.302 секунды; среднее время обработки задания сервером: 2.063 секунды; среднее число заданий в системе: 1.055; вероятность простоя системы: 0.341.

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

При имитационном моделировании системы нельзя ограничиться статистической обработкой данных, полученных при одном прогоне имитационной модели. Необходимо провести серию экспериментов с имитационной моделью, статистически обработать данные серии экспериментов для получения более обоснованных выводов. В работе предлагается рассчитать (по результатам 5-ти экспериментов с имитационной моделью системы) статистические характеристики показателя «время пребывания задания в системе» в Statistica: среднее, среднеквадратическое отклонение, медиана, минимальное и максимальное значения, размах, коэффициент вариации и построить гистограмму распределения [3,4]. Анализ статистических характеристик позволяет оценить эффективность функционирования изучаемой системы.

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

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

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

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

В случае сравнения выборок значений выходных характеристик (для двух вариантов системы) с неравными и неизвестными дисперсиями строят доверительный интервал Велча, основанный на t-критерии Стьюдента [9]. Границы доверительного интервала Велча для разности средних значений выходных характеристик для двух вариантов реализации системы вычисляются по формуле:

, (1)

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

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

– количество значений в первой и второй выборках;

– квантиль распределения Стьюдента с степенями свободы уровня

.

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

. (2)

В результате вычислений (задача примера 5) получены следующие значения: (выполнено 5 экспериментов с имитационными моделями системы, каждый эксперимент состоял из 100 испытаний); минут и минут (среднее время пребывания детали на производственном участке для первого и второго вариантов системы); и (дисперсия времени пребывания детали на производственном участке для первого и второго вариантов системы); =7.89; . Следовательно, 90-процентный доверительный интервал Велча составляет: [-2.69;0.58]. Так как доверительный интервал содержит нулевое значение, делается вывод о статистической незначимости отличий между средним временем пребывания детали на производственном участке для двух вариантов системы при уровне значимости 0.1. Таким образом, приобретение нового фрезерного станка не приведет к значимому уменьшению времени обработки детали и поэтому нецелесообразно.

Замечание. В случае если границы доверительного интервала имеют один знак, например [2.69;8.58], то делается вывод о статистической значимости отличий выходных характеристик для двух вариантов системы при заданном уровне значимости. Приобретение нового фрезерного станка приведет к уменьшению времени пребывания детали на производственном участке на величину от 2.69 до 8.58 минут.

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