Научный журнал

Современные наукоемкие технологии

ISSN 1812-7320

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

ИФ РИНЦ = 0,940

• Авторы
• Файлы

Кайнов А.С.

Статья в формате PDF

120 KB

           (1)

при следующих ограничениях:

,                                                       (2)

  .                                    (3)

Элементы x_iz плана распределения X являются непрерывными величинами и имеют следующий смысл: если x_iz=1, то z-е задание выполняется на i-м компьютере, если x_iz=0, то z-е задание на i-м компьютере не выполняется. Величина τ_iz - это время выполнения z-го задания на i-м компьютере,λ1 ,λ2 - коэффициенты целевой функции. Целевая функция (1) является сверткой двух критериев: загруженность компьютеров должна быть равномерной, суммарное время работы компьютеров должно быть минимальным.

Ограничение (2) требует, чтобы каждое задание выполнялось только на одном компьютере. Ограничение (3) требует, чтобы на -м компьютере задание  либо выполнялось целиком, либо вовсе не выполнялось.

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

                                                             (4)

Решение  имеет смысл только тогда, когда элементы вектора X принимают значения 0 или 1, поэтому решение округляется в соответствии со следующим правилом:

.             (5)

Для решения задачи (4) применяется метод Флетчера-Ривса [2], который относится к классу градиентных методов поиска приближенного решения. Метод Флетчера-Ривса состоит в построении последовательности точек {X^k}, где ,k=0,1,..., обеспечивающей убывание целевой функции (т.е. ), где точки последовательности вычисляются по правилу:

,k=0,1...,                                     (6)

а величина шага t_k определяется для каждого значения k из условия:

.                                             (7)

Решение задачи (7) сводится к нахождению корней полинома третьей степени. Направление убывания  определяется по формуле:

,                                  (8)

где вектор-градиент  целевой функции и коэффициент  определяются как:

 и .

Евклидова норма  вычисляется по формуле:

                         (9)

Алгоритм Флетчера-Ривса состоит из следующих этапов:

Входные параметры алгоритма: начальное состояние , параметры критериев останова , предельное число итераций M.

1. Установить счетчик итераций:k=0 .
2. Вычислить градиент , используя следующую формулу:. 
3. Проверить выполнение условия окончания . Если условие выполнено, то принять  и перейти на п.9.
4. Если выполняется условие k≤M, то X* = X^k и перейти на п.9.
5. Определить направление убывания  по формуле (8).
6.  Найти . Если t*_k не найден, то принять t*_k = 0.
7. Вычислить новую точку .
8. Если одновременно выполняются условия , , , , то принять X* =X ^k+1 и перейти на п.9. Иначе установить k = k+1 и перейти на п.2.
9. Округлить координаты точки  в соответствии с правилом (5).
10. Если план X*удовлетворяет ограничениям (2) и (3), то X* - найденное решение, в противном случае - решения не найдено.
11. Выход.

В работе исследовано влияние параметров алгоритма на получаемые решения и скорость работы алгоритма. Предложен способ выбора начальных точек  из окрестности центра единичного куба, т.е. . Численные эксперименты показали, что наилучшие значения Δx находятся в интервале от 0.05 до 0.2. Однако, при слишком малом Δx может возникнуть ситуация когда все точки из окрестности  будут находиться в области притяжения локальных минимумов, далеких от оптимального решения, что ограничит потенциальную возможность алгоритма найти глобальный минимум. Поэтому рекомендуется выбирать параметр Δx из диапазона [0.15;0.2].

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

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

СПИСОК ЛИТЕРАТУРЫ:

1. Дегтярев Ю.И. Исследование операций: Учеб. для вузов по спец. АСУ. - М.: Высш. шк., 1986. - 320 с.: ил.
2. Летова Т.А., Пантелеев А.В. Экстремум функций в примерах и задачах: Учебное пособие. - М.: Изд-во МАИ, 1998.-376 с.: ил.

Библиографическая ссылка