Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,087

SIMULATION AND OPTIMIZATION OF QUEUING SISTEMS

Boyarshinova I.N. 1 Ismagilov T.R. 1 Potapova I.A. 1
1 Perm National Research Polytechnical University
Предлагаемая работа посвящена компьютерному имитационному моделированию системы массового обслуживания (СМО) и оптимизации её параметров. Разработан алгоритм моделирования работы СМО с несколькими потоками заявок, наличием очереди заявок для каждого потока и ограниченным временем ожидания заявки в очереди. Производится оценка эффективности работы СМО, а также оптимизация параметров системы. Алгоритм реализован в виде компьютерной программы. Описание программы дано в виде блок-схемы с пояснениями. В качестве критерия оптимизации выбрано время нахождения заявки в очереди, варьируемыми параметрами являются количество потоков и длина очереди в системе. Работа алгоритма и компьютерной программы проверена на модельном численном эксперименте. Результаты модельного эксперимента подтверждают эффективность методов компьютерного имитационного моделирования для диагностики и оптимизации систем массового обслуживания.
The proposed work is devoted to computer simulation of queuing systems and optimization of its parameters. The algorithm of modeling work of the queuing systems with multiple streams, the presence of a queue of applications for each flow and limited time waiting in line applications is developed. The evaluation of the effectiveness of the queuing systems and optimization of the system parameters is performed. The algorithm is implemented in a computer program. Description of the program is given in the block diagram form with explanations. The linear combination of the time spent in the application queue and the number of streams is selected as a criterion for optimization. The variable parameters are the number of streams and the length of the queue in the system. The algorithm and computer program are tested in numerical simulations experiment. The results of the model experiment confirmed the effectiveness of methods of computer simulation for the diagnosis and optimization of queuing systems.
queuing systems
computer simulation
multiple streams
queue of applications
optimization of the system parameters
1. Bojarshinov A.M., Bojarshinova I.N. Kriterii optimalnosti v zadache upravlenija investicionnym portfelem / A.M. Bojarshinov, I.N. Bojarshinova // Nauchno-tehnicheskie vedomosti SPbGPU. 2012. no. 3(149), pp. 97–99.
2. Bojarshinova I.N., Drobinin M.M. Snizhenie urovnja ostatochnyh naprjazhenij v izdelijah iz polimerov putem optimizacii processa proizvodstva // Nauchno-tehnicheskij vestnik Povolzhja. 2013. no. 2, pp. 19–23.
3. Buslenko N.P., Shrejder Ju.A. Metod statisticheskih ispytanij (Monte-Karlo) i ego realizacija na cifrovyh vychislitelnyh mashinah. M.: Gosudarstvennoe izdatelstvo fiziko-matematicheskoj literatury, 1961. рp. 226.
4. Ventcel E.S. Issledovanie operacij Izdatelstvo «SOVETSKOE RADIO» Moskva. 1972. рp. 552.
5. Ermakov S.M., Mihajlov G.A. Statisticheskoe modelirovanie. 2-e izd., dopoln. M.: Glavnaja redakcija fiziko-matematicheskoj literatury izdatelstva «Nauka», 1982 g. рp. 296.
6. Chernoruckij I.G. Metody prinjatija reshenij. SPb.: BHV-Peterburg, 2005. рp. 416.

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

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

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

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

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

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

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

● эффективность работы всех потоков, условием которой является выполнение следующего неравенства:

K∙PMAX < Pi,

где Pi – производительность i-го потока; PMAX – максимальная производительность среди всех потоков; K – коэффициент, заданный пользователем (0 ≤ K ≤ 1).

Блок-схема программы представлена на рис. 1. Моделирование производилось для количества дней Days.

Все данные о потоках (текущее количество заявок в потоке; данные об обрабатываемой заявке и каждой заявке в очереди: время поступления заявки в поток; время начала обработки; время, необходимое для обработки конкретной заявки) хранятся в массиве Streams. В зависимости от момента времени определяется, окончена ли работа системы на текущий «день».

В блоке 1 все потоки проверяются на завершённость обработки текущей заявки. Если обработка текущей заявки окончена, в случае наличия очереди на обработку поступает следующая заявка.

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

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

Результаты каждой итерации сохраняются. Статистическая обработка всех результатов производится методом Монте-Карло [3, 5]. Количество повторений изменяется от 500 до 10000 с шагом 500.

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

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

Среднее время пребывания в очереди в многопоточной системе с ожиданием может быть выражено как [4]

boayrshin01.wmf (1)

где tср – среднее время пребывания заявки в очереди; p0 – вероятность того, что поток свободен; boayrshin02.wmf; λ – интенсивность приходящих заявок; μ – интенсивность обслуживания; n – количество каналов; m – количество мест в очереди, boayrshin03.wmf.

В качестве целевой функции оптимизации выберем обобщенный критерий [1, 2], содержащий среднее время пребывания в очереди (1) и функцию количества потоков. Целевая функция примет вид

boayrshin04.wmf (2)

где nmax – максимальное число каналов; К – весовой коэффициент.

Параметрами оптимизации выступают количество потоков и количество мест в очереди.

В качестве метода оптимизации выбран метод Нелдера – Мида [6] как наиболее универсальный и слабо чувствительный к количеству переменных, что позволяет при необходимости менять количество параметров оптимизации.

pic_1.wmf

Рис. 1. Блок-схема компьютерной программы

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

количество потоков – 6;

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

максимальное время ожидания в очереди – 8,0;

максимальное время обработки одной заявки – 1,8;

доля загруженности канала, при которой его работа считается эффективной – 75 %;

допустимая доля необработанных заявок составляет 10 %.

pic_2.tif

Рис. 2. Результат работы процедуры моделирования работы СМО

pic_3.tif

Рис. 3. Результат работы процедуры оптимизации параметров СМО

Результаты моделирования работы системы и оптимизации её параметров представлены на рис. 2 и 3.

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

В результате решения задачи оптимизации (2) получены следующие оптимальные параметры системы: число потоков – 5, число заявок в очереди – 5. Моделирование системы с оптимальными параметрами показало, что количество неэффективных потоков снизилось до трех. Общие затраты компьютерного времени на имитационное моделирование и оптимизацию системы составили 20 с.

Корректность предложенного алгоритма и работы программы проверена на тестовой задаче [4]. Условия тестовой задачи: автозаправочная станция (АЗС) с двумя колонками (n = 2) предназначена для обслуживания машин. Поток машин, прибывающих на АЗС, имеет интенсивность две машины в минуту (λ = 2); среднее время обслуживания одной машины – 2 минуты. Площадка АЗС может вместить очередь не более трёх машин (m = 3). Машина, прибывшая в момент, когда все места в очереди заняты, покидает АЗС (получает отказ).

В работе [4] рассчитаны теоретические вероятности отказа и обработки:

Pот = 0,512; Pоб = 0,488.

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

Pот = 0,559; Pоб = 0,441.

Теоретически рассчитанное среднее число занятых каналов z = 1,952.

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

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

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

Рецензенты:

Столбов В.Ю., д.т.н., профессор, декан факультета прикладной математики и механики, профессор кафедры ММСП, Пермский национальный исследовательский политехнический университет, г. Пермь;

Сметанников О.Ю., д.т.н., доцент кафедры вычислительной математики и механики, Пермский национальный исследовательский политехнический университет, г. Пермь.