3. Алгоритмы списочных расписаний

1Алгоритм Крона

Принцип действия алгоритма Крона можно описать в два этапа. Первый этап заключается в случайном распределении множества заданий на множество приборов, второй этап уточняет полученное распределение. Алгоритм первого этапа можно представить в виде последовательности шагов:

Ш1. Сгенерировать случайное число p_i – номер прибора, равномерно распределённое на интервале [1,N]. Инициализировать j = 1.

Ш2. Назначить на прибор с номером p_i j-ое задание. Увеличить j = j + 1.

Ш3. Проверить, больше ли значение j количества заданий M. Если условие выполняется, то прекратить распределение, а иначе перейти к шагу 1.

Второй этап – уточнение, включает следующие шаги:

Ш1. Вычислить время загрузки каждого прибора {T_j} ( j = 1,..,N ) путем суммирования времен выполнения заданий загруженных в каждый j-й прибор.

Ш2. Из полученного множества {T_k} выбрать номера приборов с максимальным T^max и минимальным T^min значениями из набора {T_k} соответственно.

Ш3. Для каждого прибора с минимальной и максимальной загрузкой проверить условие по принципу каждый с каждым

t_k^max – t_l^min < ,

где  = T^max - T^min, k,l = 1,.., M. При этом t_k^max > t_l^min.

Если условие выполняется, то перейти к следующему шагу, а иначе прекратить выполнение алгоритма.

Ш4. Переставить значения t_k и t_l местами и перейти к шагу 1.

Решим задачу №1 алгоритмом Крона:

Ш1. Генерируется число i из интервала [1,3]. Пусть i = 2. Согласно Ш.2 На устройство назначается для выполнения j-е задание, на текущей итерации j = 1, т.е. . Расписание на 1-вом шаге:

Генерируем номер следующего прибора, пусть i = 3 т.е. . Назначаем следующую по порядку работу Расписание на 2-ом шаге примет вид:

И снова генерируем номер следующего прибора, пусть i = 2 т.е. . Назначаем следующую по порядку работу Расписание на 3-ем шаге примет вид:

Выполнив все итерации, получаем расписание R

Далее выполняем второй этап алгоритма Крона. На шаге 1 вычисляем время загрузки каждого прибора.

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

Так же нужно организовать проверку: нет ли среди заданий прибора (с максимальной загрузкой) время выполнения которых меньше .

В данном случае такое задание есть t₁^max < . Поэтому это задание переходит в прибор и распределение заданий выглядит следующим образом:

Снова пересчитываются значения загрузки приборов и выбираются приборы с максимальной и минимальной загрузкой. При данных значениях это и соответственно. Осуществляется проверка: нет ли среди заданий прибора (с максимальной загрузкой) время выполнения которых меньше . При данных значениях времени выполнения заданий, загруженных в и значения  = 2, таких заданий нет.

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

t_k^max – t_l^min < .

При этом важно, чтобы t_k^max > t_l^min.

Начнём проверку с первого задания, загруженного в прибор . Проверяем условие 5 > 22 – ложь. Переходим к следующему заданию и проверяем условие 15 > 22 – выражение ложно. Опять берём следующее задание и проверяем условие 4 > 22 – ложь.

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

Итак, в результате выполнения итераций, получено расписание R

Критерий оценки алгоритма – максимальное время завершения выполнения работ: =24