Оптимизация распределения нагрузки при реализации взаимодействий в системе

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

Будем называть технологическим объектом (ТО) некоторую обособленную материальную единицу, рассматриваемую в процессе осуществления взаимодействий между узлами системы как единое целое. Физическая природа ТО может быть различной для разных РТС. В производственной системе, например, в качестве ТО могут выступать отдельные комплектующие, а также целые изделия. В информационной системе в качестве ТО могут рассматриваться массивы данных, отдельные программы, в коммерческой системе — отдельные предметы потребления или их наборы.

Пусть Х{. — интенсивность внешних запросов на i-й ТО, возникающих в узле j, где 1,/ j = 1, J и г соответствует номеру ТО, a j — номеру узла.

Собственно числовое значение Х{. уже задает определенную информацию о характере ТО. Так, в производственной системе, где запросы поступают только на готовые изделия, А,„=0 для всех г, соотносимых с комплектующими ТО; в информационной системе Х{. можно полагать равным 0 для массивов данных и программ, обращение к которым возможно лишь из других программ. При этом Х{ 0 лишь для тех г, которые определяют головные программы.

В целях унификации терминологии подобные ТО будем называть головными вне зависимости от сферы их принадлежности (производственной, информационной, коммерческой и т. д.). Иными словами, головной ТО — это такой ТО, который является основой реализации запроса пользователя.

При выполнении запроса на головной ТО необходимо знать, какие другие ТО необходимы для удовлетворения этого запроса. Такое отношение будем определять с помощью матрицы А = {aj, где

1,если при обработке /-го ТО необходимо выполнить обраще-

„ ние за к-м;

aik = ?

О в противном случае.

Для удобства дальнейших построений целесообразно положить а& = 1.

Кроме того, для более полного отражения реальной действительности помимо запросов на использование ТО необходимо ввести запросы на корректировку ТО. Физически это означает, например, пополнение запасов хранения ТО в производственной системе либо корректировку хранимых данных в информационной системе. Для определенности будем такие запросы называть донесениями.

Рассмотрим вначале случай, когда обращения (взаимодействия) между узлами РТС связаны лишь с запросами на выдачу хранимых ТО, а вся обработка (сборка) производится в узлах, из которых исходят обращения. Иными словами, распределение нагрузки в РТС в данном случае лишь предполагает распределенное хранение ТО.

Распределение ТО для хранения в системе можно осуществлять различными способами. При этом эффективность функционирования системы может существенно меняться.

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

Введем переменную хк., определяемую следующим образом:

Г1, если к-й ТО хранится в j-м узле; xkj ~ 0 в противном случае.

При этом полагается, что весь набор ТО обязательно хранится в ОУ, а корректировка ТО осуществляется последовательно для всех хранимых в системе ТО. Тогда суммарный объем взаимодействия в системе выразится следующим образом:

где V. и v' — средний объем одного взаимодействия при обра-

к у i

ботке соответственно запросов и донесений.

В этом случае математическую модель задачи можно сформулировать в следующем виде.

Найти такой набор значений Х*= {х*1^}, при котором при ограничениях

где к и V. — физический объем, занимаемый к-м ТО и емкость j-то узла соответственно;

пк — оптимальная степень дублирования ТО.

Полагаем, что ф 0 лишь для головных ТО. Последние обрабатываются обязательно в j-м узле, при этом суммарная загрузка узла не должна превышать допустимой. Величина этой загрузки может быть рассчитана заранее (поскольку известны) и учтена при выборе состава технических средств узлаэ Решение задачи (4.17)—(4.19) является исходной информацией для определения числа ОУ в системе. В самом деле, полагая, что заявки на использование и корректировку к-то ТО характеризуются затратами соответственно тк и т'. ОУ, можно вычислить суммарную загрузку р всех ОУ:

При этом, как отмечалось выше, полагается, что все ТО дублируются в ОУ (в противном случае второй член в (4.20) будет

иметь вид ? ? (1 - x,j )Х т').

' у и

Рассчитаем следующие величины:

где F=?co,.;

/

Уф — емкость одного ОУ, используемая для хранения ТО; ркр — допустимая предельная загрузка одного ОУ. Отсюда необходимое количество ОУ определяется следующим образом:

Рассмотрим следующий случай. Пусть в системе имеются 4 ИУ и должно храниться 10 ТО. Емкость пространства, выделяемого для хранения ТО в ИУ такова, что возможно хранение одновременно лишь не более трех ТО (например, V. = 1500, j= 1, 4, а со^ = 500, к = 1, Ю) • Величинып{ = 1, i = 1, 10. Значение элементов матрицы А приведены в таблице 4.3.

Таблица 4.3 — Состав технологических объектов

Номера го- ловных ТО

Номера ТО, используемых при обработке головных ТО

1

2

3

4

5

6

7

8

9

10

1

1

1

-

1

-

-

-

-

-

1

3

-

-

1

1

-

1

-

-

1

-

5

-

1

-

1

1

-

-

1

1

1

7

-

-

-

-

-

1

1

1

-

-

В таблице 4.4 представлены значения величины ^.(числитель) и Х'у (знаменатель). По структуре информации в строках таблицы 4.3 видно, что ТО 1, 3, 5 и 7 являются головными , ТО 4, 8, 9,10 —- корректируемыми, а ТО 2 и 6 — условно корректируемыми. Причем задано, что v( = 500 при запросе ТО, V, =50 при корректировке ТО.

Таблица 4.4 — Интенсивности взаимодействия {. / X]j)

Номер ТО

Номер узла

1

2

3

4

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 500/—
  • 1/-
  • 1/-
  • -/1
  • -/100
  • 5/-
  • 1/-
  • 500/-
  • -/100
  • 20/—
  • 500/—
  • -/100
  • 1/-
  • -/100
  • -/1
  • 10/-
  • 5/-
  • -/1
  • 100/—
  • 1/-
  • -/1

Полученное в соответствии с (4.16)—(4.19) решение оптимизационной задачи представлено в таблице 4.5.

Данное решение обеспечивает минимальный удельный объем взаимодействий в системе, равный 604950 (564400 по реализации запросов и 40550 — по корректировке).

Для сравнения укажем, что для случая, когда все ТО хранятся только лишь в ОУ, объем взаимодействий в системе составляет 2734000 (2718800 + 15200), т. е. более чем в 4,5 раза больше.

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

В соответствии с (4.21) и (4.22) получаем, что Np = 1, Nv = 1, т. е. в системе достаточно иметь один ОУ. В то же время в случае размещения всех ТО только в ОУ iVp= 2. Nv = 1 и N = = max {2,1}=2, т. е. необходимо два ОУ.

Таблица 4.5 — Решение оптимизационной задачи

Номер ТО

Номер узла

1

2

3

4

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1

Следовательно, рациональное размещение ТО в системе приводит не только к уменьшению взаимодействий в системе, что само по себе дает экономический эффект, но и к уменьшению числа ОУ. Это также дает экономию затрат.

Теперь рассмотрим случай, когда ОУ обеспечивает обработку ТО так, что ряд запросов реализуется в ОУ, а именно те запросы, головные ТО которых отсутствуют в соответствующих ИУ. Целевая функция для данного случая запишется следующим образом:

где vio ?— объем взаимодействий с ИУ при реализации запросов в ОУ; при этом полагается, что все ТО также дублируются в ОУ.

Математическая модель данной задачи запишется следующим образом:

Здесь соотношения (4.28) и (4.29) связаны с необходимостью обеспечения ограничений на предельную загрузку соответственно ИУ и ОУ. Причем (4.29), по сути, неявно задает предельное число ОУ.

Рассмотрим расширенный случай. Пусть значения vio задаются в таблице 4.6.

Таблица 4.6 — Значения vjo

Номера головных TO

1

3

5

7

Значения V.

Ю

10

1000

10

100

Задано также р. = 0,65 для j = 1, 4; рс =0,53; т.. = 0,001 для г = 1 10, j = 1, 4; тс = 0,002.

Решение задачи (4.25)-(4.29) дает следующий результат. Обработка ТОЗ выполняется на ИУЗ; Т07— на ИУ2. Для TOl и Т05 обработка выполняется на ОУ.

При этом суммарный объем взаимодействий в системе будет равен 39770 (14370 по запросам и 25400 — по корректировав ке). Если же вся обработка реализуется только в ОУ, то объем взаимодействий в системе составляет 1041570 (1021370 + 20200).

Таким образом, при последнем варианте функционирования системы объем взаимодействий увеличивается примерно в 26 раз. Для реализации оптимального варианта требуется 20У, в альтернативном варианте — 3. Налицо значительный выигрыш.

Рассмотрим теперь особенности рассмотренных задач, возникающие в некоторых конкретных прикладных сферах.

Допустим, что организация занимается обеспечением региональных центров некоторыми изделиями (запасными частями к агрегатам, собственно агрегатами и другими громоздкими изделиями). Известна интенсивность запросов X.. на г-е изделие, i = 1,1 (в неделю, в месяц и т. п.). В региональных центрах имеются лишь ограниченные возможности по складированию изделий — W. j = 1 ,J. Задача заключается в рациональной поставке изделий в регионы, т. е. обеспечение регионов изделиями должно осуществляться таким образом, чтобы запросы на них по возможности удовлетворялись на месте. При такой постановке задачи ее математическая модель, в целом похожая на модель (4.17)—(4.19), имеет несколько упрощенный вид по сравнению с последней.

При этом целевая функция (критерий) имеет следующий

вид:

а система ограничений в общем виде запишется так:

где х{. — булева переменная, единичное значение которой определяет необходимость предварительного хранения (поставки) г-го изделия в j-м центре;

W. — возможность j-то центра по хранению изделий;

0)^ — объем запроса на хранение г-го изделия (например, занимаемая площадь);

v{j — потери, связанные с отсутствием г-го изделия при поступлении запроса на них в j-й центр.

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

где at. — булева величина, единичное значение которой определяет обязательную предварительную поставку г-х изделий в j-й центр;

N. — количество таких изделий (обязательной поставки для j-то центра).

Рассмотрим теперь более сложную задачу, связанную с размещением производственных мощностей по выпуску некоторого ассортимента изделий i = 1,7, в регионах j = 1, J, где на них существует спрос Для каждого изделия имеются две

возможности: его производство в регионе либо закупка на стороне (например, за рубежом). Второе решение обходится дороже первого на vjk для некоторого к-то комплектующего г-го изделия и на величину vjo — для всего изделия. Необходимо отыскать наиболее рациональное решение (в плане стоимости).

Целевая функция математической модели по аналогии с (4.24) запишется следующим образом: i

Здесь булева величина ajk характеризует наличие к-то комплектующего (ajk = 1) в изделии г.

В общем случае математическую модель задачи можно сформулировать таким образом:

Здесь W!—- потребные ресурсы ?-го типа для производства г-х изделий; V1. — наличные ресурсы ^-го типа в регионе j.

Булевы величины и У,7 задают обязательность либо невозможность производства г-го изделия в j-м регионе, если по каким-то причинам это установлено заранее. Возможны и другие ограничения в модели, вызванные учетом реальных факторов.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >