Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

Рассматривается задача оптимального распределения n заданий по l компьютерам мультипроцессорной системы [1]. Необходимо определить план распределения заданий , обеспечивающий минимум целевой функции:

           (1)

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

,                                                       (2)

  .                                    (3)

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

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

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

                                                             (4)

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

.             (5)


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

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

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

.                                             (7)

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

,                                  (8)

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

 и .

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

                         (9)

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

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

  1. Установить счетчик итераций:k=0 .
  2. Вычислить градиент , используя следующую формулу:. 
  3. Проверить выполнение условия окончания . Если условие выполнено, то принять  и перейти на п.9.
  4. Если выполняется условие k≤M, то X* = Xk и перейти на п.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 с.: ил.