<<
>>

Разработка алгоритма

Начнем с рассмотрения очень простого жадного алгоритма. Алгоритм перебирает задания в любом порядке за один проход; когда очередь доходит до задания j, оно назначается на машину с минимальной на данный момент нагрузкой.

Greedy-Balance:

В начале назначенных заданий нет Присвоить T = 0 и A(i) = 0 для всех машин M For j = 1............. n

Пусть Mi - машина с минимальным minkTk Назначить задание j на машину M

Присвоить A(i) ^ A(i) U {/}

Присвоить Ti ^ T. + t.

Конец For

На рис. 11.1 показан результат выполнения этого жадного алгоритма для по- следовательности из шести заданий с размерами 2, 3, 4, 6, 2, 2; полученный период обработки равен 8 («высота» заданий на первой машине). Обратите внимание: это решение не является оптимальным; если бы задания поступили в другом порядке и были получены алгоритмом в последовательности 6, 4, 3, 2, 2, 2, то было бы полу- чено назначение с периодом обработки 7.

Рис. 11.1. Результат выполнения жадного алгоритма распределения нагрузки на трех машинах с размерами заданий 2, 3, 4, 6, 2, 2

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007