Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ABOUT AN APPROACH TO THE RESOURCE ALLOCATION, MINIMIZING THE VOLUME OF APPLICATIONS WITH A SPECIFIED TIMEOUT

Maksimov D.A. 1 Khalikov M.A. 1
1 Plekhanov Russian University of Economics
The problem of limited resources allocation for implementation of scheduled volume costs in open queuing networks is considered. For example, in the areas of machining process of large engineering industry. It is shown that by using the criterion of minimizing the volume of raw applications with a fixed latency at the end of the planning period, the original problem reduces to linear programming problem of high dimensionality, which relevant to the research of the stability of the optimal solution for the arrival rate of applications. In the research the relevant definitions and attributes of stable solutions are given, the stability problem of optimal resources allocation against the initial data model and the arrival rate of applications is researched in order to minimize the time spent by applications in the system.
attributes of optimal solutions
stability of optimal solution
linear programming problem
waiting time of application
resource allocation
arrival rate of applications
open queuing networks
Одной из актуальных задач для открытых систем массово­го обслуживания является распределение ограниченных ресурсов при вы­полнении запланированных объемов работ. Такие задачи встречаются, например, при обработке данных в АСУТП, где поступающая информация (сигналы от датчиков) должна быть обработана в режиме реального времени или при обработке партий деталей по заданной маршрутной технологии на участках взаимозаменяемого оборудования разной производительности.

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

В качестве критерия оперативности обработки заявок в открытой сис­теме обслуживания,как правило,рассматриваетсядоля заявок, время ожидания которых не менее заданного τ [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) при различных интенсивностях входно­го потока заявок, связанных с выбором времени ожидания, по которому производится максимизация обработанного объема заявок.

Рецензенты:

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

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