Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Алгоритм Крона
Принцип действия алгоритма Крона можно описать в два этапа. Первый этап заключается в случайном распределении множества заданий на множество приборов, второй этап уточняет полученное распределение. Алгоритм первого этапа можно представить в виде последовательности шагов: Ш1. Сгенерировать случайное число pi – номер прибора, равномерно распределённое на интервале [1,N]. Инициализировать j = 1. Ш2. Назначить на прибор с номером pi j-ое задание. Увеличить j = j + 1. Ш3. Проверить, больше ли значение j количества заданий M. Если условие выполняется, то прекратить распределение, а иначе перейти к шагу 1. Второй этап – уточнение, включает следующие шаги: Ш1. Вычислить время загрузки каждого прибора {Tj} ( j = 1,..,N ) путем суммирования времен выполнения заданий загруженных в каждый j-й прибор. Ш2. Из полученного множества {Tk} выбрать номера приборов с максимальным Tmax и минимальным Tmin значениями из набора {Tk} соответственно. Ш3. Для каждого прибора с минимальной и максимальной загрузкой проверить условие по принципу каждый с каждым tkmax – tlmin < D, где D = Tmax - Tmin, k,l = 1,.., M. При этом tkmax > tlmin. Если условие выполняется, то перейти к следующему шагу, а иначе прекратить выполнение алгоритма. Ш4. Переставить значения tk и tl местами и перейти к шагу 1.
Решим задачу №1 алгоритмом Крона: Ш1. Генерируется число i из интервала [1,3]. Пусть i = 2. Согласно Ш.2 На устройство назначается для выполнения j-е задание, на текущей итерации j = 1, т.е. . Расписание на 1-вом шаге: Генерируем номер следующего прибора, пусть i = 3 т.е. . Назначаем следующую по порядку работу Расписание на 2-ом шаге примет вид: И снова генерируем номер следующего прибора, пусть i = 2 т.е. . Назначаем следующую по порядку работу Расписание на 3-ем шаге примет вид: Выполнив все итерации, получаем расписание R Далее выполняем второй этап алгоритма Крона. На шаге 1 вычисляем время загрузки каждого прибора. На следующем шаге в соответствие с полученным множеством выбираем приборы с максимальной и минимальной загрузкой, т.е. получаем первый и второй приборы. Так же нужно организовать проверку: нет ли среди заданий прибора (с максимальной загрузкой) время выполнения которых меньше D. В данном случае такое задание есть t1max < D. Поэтому это задание переходит в прибор и распределение заданий выглядит следующим образом: Снова пересчитываются значения загрузки приборов и выбираются приборы с максимальной и минимальной загрузкой. При данных значениях это и соответственно. Осуществляется проверка: нет ли среди заданий прибора (с максимальной загрузкой) время выполнения которых меньше D. При данных значениях времени выполнения заданий, загруженных в и значения D = 2, таких заданий нет. Теперь можно организовать перебор заданий, загруженных в первый и второй прибор по принципу каждый с каждым и проверять условие tkmax – tlmin < D. При этом важно, чтобы tkmax > tlmin. Начнём проверку с первого задания, загруженного в прибор . Проверяем условие 5 > 22 – ложь. Переходим к следующему заданию и проверяем условие 15 > 22 – выражение ложно. Опять берём следующее задание и проверяем условие 4 > 22 – ложь. Поскольку условие ни разу не выполнилось, следовательно, ни одной перестановки не совершалось, а значит, никаких улучшений в распределении сделать нельзя и алгоритм завершает свою работу. Итак, в результате выполнения итераций, получено расписание R Критерий оценки алгоритма – максимальное время завершения выполнения работ: =24
Дата добавления: 2014-12-09; просмотров: 234; Нарушение авторских прав Мы поможем в написании ваших работ! |