В повседневной жизни мы ежедневно сталкиваемся с множеством различных процессов и систем. Широкое распространение в настоящее время получили системы массового обслуживания.
При недостаточно эффективной работе системы возникает необходимость её модификации, связанной с поиском параметров системы, которые обеспечат ее работу. Задача поиска оптимальных параметров системы достаточно сложна. Ведь зачастую изменение хотя бы одного параметра требует немалых затрат, да и результат не всегда гарантирован.
В настоящее время разработано достаточно большое количество методов расчета СМО. Большинство методов расчета параметров СМО не являются универсальными, но каждый из методов имеет свои ограничения на применение, например учитывают только экспоненциальный закон распределения для времени обслуживания. В таких ситуациях на помощь приходит компьютерное имитационное моделирование, позволяющее произвести эксперимент с системой, имеющей любой входной поток заявок. Моделирование больших и сложных систем требует немало вычислительных ресурсов. Задача перебора всех возможных вариантов и сегодня является одной из самых сложных, не говоря о том, чтобы на каждую возможную комбинацию производить сложный и затратный по времени процесс моделирования. Большинство систем можно рассматривать как систему массового обслуживания с различными параметрами: количеством потоков, длиной очереди и временем ожидания. Наиболее распространённой является система с несколькими потоками, наличием очереди и ограниченным временем ожидания. По результатам диагностики с помощью имитационной компьютерной модели можно выявить слабые места и попытаться устранить их, варьируя параметры системы. С точки зрения вычислительных ресурсов нерационально моделировать каждый вариант настройки системы, поэтому логичным является привлечение методов оптимизации для экономии вычислительных ресурсов.
В данной работе была поставлена задача создания компьютерной программы, моделирующей работу СМО с несколькими потоками заявок, наличием очереди заявок для каждого потока и ограниченным временем ожидания заявки в очереди. По результатам моделирования должна производиться оценка эффективности работы системы и, при необходимости, оптимизация ее параметров.
В процессе исследования была реализована процедура, моделирующая работу СМО, результатом которой являются статистические данные для оценки работы СМО. Входной поток заявок может иметь любое распределение. Оценка эффективности работы системы производилась по нескольким критериям:
● процент заявок, не дождавшихся обслуживания, не должен превышать заданного значения;
● процент заявок, которым не хватило места в системе, т.к. все потоки были заняты, не должен превышать заданного значения;
● эффективность работы всех потоков, условием которой является выполнение следующего неравенства:
K∙PMAX < Pi,
где Pi – производительность i-го потока; PMAX – максимальная производительность среди всех потоков; K – коэффициент, заданный пользователем (0 ≤ K ≤ 1).
Блок-схема программы представлена на рис. 1. Моделирование производилось для количества дней Days.
Все данные о потоках (текущее количество заявок в потоке; данные об обрабатываемой заявке и каждой заявке в очереди: время поступления заявки в поток; время начала обработки; время, необходимое для обработки конкретной заявки) хранятся в массиве Streams. В зависимости от момента времени определяется, окончена ли работа системы на текущий «день».
В блоке 1 все потоки проверяются на завершённость обработки текущей заявки. Если обработка текущей заявки окончена, в случае наличия очереди на обработку поступает следующая заявка.
В блоке 2 в каждом потоке проверяется, не покинула ли очередь какая-нибудь из заявок и, в зависимости от результатов проверки, происходит смещение заявок в очередях.
В блоке 3 все потоки проверяются на наличие «свободного» потока (у которого отсутствует очередь и который не обрабатывает заявку в данный момент). Если «свободный» поток не найден, происходит поиск потока, имеющего свободное место в очереди, и заявка попадает в очередь. Если все места в очереди каждого потока заняты, то заявка остаётся необработанной.
Результаты каждой итерации сохраняются. Статистическая обработка всех результатов производится методом Монте-Карло [3, 5]. Количество повторений изменяется от 500 до 10000 с шагом 500.
Результаты работы системы проверяются по критериям эффективности. Если работа системы не удовлетворяет всем условиям эффективности, то подключается блок оптимизации.
Основной целью оптимизации является нахождение таких параметров системы, которые обеспечивают наименьшее среднее время нахождения заявки в очереди при минимальном количестве потоков в системе, что приводит к двухкритериальной задаче оптимизации с противоречивыми критериями.
Среднее время пребывания в очереди в многопоточной системе с ожиданием может быть выражено как [4]
(1)
где tср – среднее время пребывания заявки в очереди; p0 – вероятность того, что поток свободен; 
; λ – интенсивность приходящих заявок; μ – интенсивность обслуживания; n – количество каналов; m – количество мест в очереди, 
.
В качестве целевой функции оптимизации выберем обобщенный критерий [1, 2], содержащий среднее время пребывания в очереди (1) и функцию количества потоков. Целевая функция примет вид
(2)
где nmax – максимальное число каналов; К – весовой коэффициент.
Параметрами оптимизации выступают количество потоков и количество мест в очереди.
В качестве метода оптимизации выбран метод Нелдера – Мида [6] как наиболее универсальный и слабо чувствительный к количеству переменных, что позволяет при необходимости менять количество параметров оптимизации.
Рис. 1. Блок-схема компьютерной программы
Для оценки правильности работы предложенного алгоритма и компьютерных программ был проведён численный эксперимент по имитационному моделированию и оптимизации СМО со следующими параметрами:
количество потоков – 6;
длина очереди – 4;
максимальное время ожидания в очереди – 8,0;
максимальное время обработки одной заявки – 1,8;
доля загруженности канала, при которой его работа считается эффективной – 75 %;
допустимая доля необработанных заявок составляет 10 %.
Рис. 2. Результат работы процедуры моделирования работы СМО
Рис. 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 %, т.е. больше половины поступивших заявок были не обслужены, можно сделать вывод, что оба канала постоянно были загружены, что совпадает с теоретическим результатом. Результаты тестовой задачи подтверждают корректность работы алгоритма и компьютерной программы.
Разработан алгоритм имитационного моделирования работы СМО с несколькими каналами, ограничением на длину очереди и время ожидания в очереди. На основании алгоритма написана программа, моделирующая работу СМО и оценивающая её эффективность. Для нахождения оптимальных параметров системы поставлена задача оптимизации и реализован алгоритм её решения методом Нелдера – Мида.
Проведенный эксперимент показал, что затраты компьютерного времени, считающиеся основным недостатком имитационного моделирования, не являются критичными при реальных параметрах СМО. Полученные результаты подтверждают эффективность методов компьютерного имитационного моделирования для диагностики и оптимизации систем массового обслуживания.
Рецензенты:
Столбов В.Ю., д.т.н., профессор, декан факультета прикладной математики и механики, профессор кафедры ММСП, Пермский национальный исследовательский политехнический университет, г. Пермь;
Сметанников О.Ю., д.т.н., доцент кафедры вычислительной математики и механики, Пермский национальный исследовательский политехнический университет, г. Пермь.