Сетевое издание

Современные проблемы науки и образования

ISSN 2070-7428

"Перечень" ВАК

ИФ РИНЦ = 1,006

Одной из актуальных задач для открытых систем массово­го обслуживания является распределение ограниченных ресурсов при вы­полнении запланированных объемов работ. Такие задачи встречаются, например, при обработке данных в АСУТП, где поступающая информация (сигналы от датчиков) должна быть обработана в режиме реального времени или при обработке партий деталей по заданной маршрутной технологии на участках взаимозаменяемого оборудования разной производительности.

Общим для этих задач являются ограниченность ресур­сов, на которых обрабатываются заявки (сигналы, детали), и цель– миними­зация времени нахождения заявок в системе (время ожидания плюс вре­мя обслуживания).

В качестве критерия оперативности обработки заявок в открытой сис­теме обслуживания,как правило,рассматриваетсядоля заявок, время ожидания которых не менее заданного τ [1] .

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

 

Рис. 1. Граф-структура технологии обработки заявок

 

Технологию обработки заявок в открытой системе будем представлять ориентированным ациклическим графомG= G(M,N) (рис.1),где:

N– вер­шины (различные операции обработки заявок);

М – дуги (возможные последовательности обработки заявок на заданном множестве операций) с выделенными вершинами;

– источник заявок;

– сток обработан­ных заявок;

К – множество конечных (завершающих) операций обработки;

– множество операций-предшественников для операции .

Фиксируем следующие параметры:

Т – установленный для исследуемой системы временной интервал (мин, час, сутки);

– (кратное Т) — максимальное время пребывания заявки в очереди;

– (кратное Т) — продолжительность периода, на котором распределяются ресурсы (директивный период).

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

Выполнение обработки операций технологического цикла осуществ­ляется на Рединицах оборудования, производительности которых задают­ся матрицей размерности NxP, где– производительность p-го оборудования на i-й операции ( в случае, если i-я операция наp-м оборудовании не осуществляется).

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

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

В такой постановке задача может быть сведена к задаче распределения ресурсов по критерию максимизации общего объема обработанных за директивный период заявок. Для этого достаточно рассмотреть среди всех заявок, находящихся в очередях , и среди заявок, поступающих на обра­ботку .  «Возраст»  которых к окончанию периода [0,] будет не менее .

Исходя из этого положения примем в качестве входного потока заявок следующий:

                                                                                            (1)

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

                                                                                                                          (2)

Обозначим - частьj-го интервала, в течение которого р-еобору­дование выполняетi-ю операцию.

Задача минимизации объемов необработанных заявок со временем ожидания к концу директивного периода не менее т может быть сформу­лирована как следующая оптимизационная (относительно ) задача:

                                                                                              (3)

при ограничениях

                                                 (4)

i=1,…,N; j=1,…,(условие баланса очередей);

                                                                                (5)

j=1,…,; p=1,…,P(условие баланса оборудования).

Задача (3)—(5), учитывая линейность функционала и ограничений, относится к задачам линейного программирования (ЛП).

Рассмотрим, как изменяется значение функционала(3) при изменении интенсивности потока входных заявок.

Фиксируем целое , большее 0.

Определение 1. Задача (3)—(5) – устойчива по интенсивности по­ступления заявок , если для всех точек окрестности (,)значение функционала (1) остается неизменным.

Определение 2. Максимальное, при котором задача (3)—(5)  — устойчива по интенсивности поступления заявок, назовем радиусом ус­тойчивости задачи по интенсивности входного потока заявок.

Пусть– решение задачи (3)-(5) и значение функционала (3) прираспределенияравно . Определить диапазон изменения интенсивно­сти входного потока заявок можно, решив следующие задачи ЛП отно­сительно  и :

;                                                                                                                                (6)

                                                                                                              (7)

                                                (8)

i=1,…,N; j=1,…,;

                                                                                            (9)

j=1,…,; p=1,…,P.

;                                                                                                                                 (10)

                                                                                                           (11)

                                                   (12)

i=1,…,N; j=1,…,;

                                                                             (13)

j=1,…,; p=1,…,P.

Радиус устойчивости исходной задачи (3)-(5) по интенсивности входного потока заявок определим по формуле:

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

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

                                                                                         (15)

                                                                 (16)

i=1,…,N; j=0,…,L-1;

                                                                  (17)

j=0,…,L-1; p=1,…,P.

Примечание.– часть интервала , на котором p-еоборудование использу­ется на i-й операции; – объем очереди на i-й операции в начале ин­тервала .

В случаеесли производительности каждой из Pединиц оборудования на рассматриваемом интервале не превышают интенсивностей поступле­ния заявок, решение задачи (15)—(17) дает оптимальное по производи­тельности распределение оборудования.

Обратно, если производительность каждой единицы оборудования на рассматриваемом интервале превышает интенсивность поступле­ния заявок, то, разрешив кольцевую процедуру переключения оборудова­ния с одной операции на другую [5], можно сохранить распределение соот­ветствующей ЛП-задачи и обработанный объем заявок сделать сколь угод­но близким к значению Афункционала (13). Докажем этот факт. Выберем .Для того, чтобы получить распределение оборудования по опера­циям на интервале ,которое даст объем обработанных заявок , поступим следующим образом. Разобьем интервал  на подинтервалы длиной  и на каждом из подинтервалов сохраним распределение, полученное в задаче (15)—(17), сокра­тив время работы каждой единицы оборудования в раз. Вэтом случае производительность оборудования на каждом из полученных подинтервалов (за исключением, быть мажет, первого) будет равна , что и доказывает сформулированное утверждение.

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

Рецензенты:

Загородников С.Н., д.б.н., профессор, профессор кафедры «Математические методы в экономике» ФГБОУ ВПО «Российский экономический университет имени Г.В. Плеханова», г.Москва;

Титов В.А., д.э.н., профессор кафедры «Информационные технологии» ФГБОУ ВПО «Российский экономический университет имени Г.В. Плеханова», г.Москва.