Исследование алгоритма Крона и его модификации при различных исходных данных

Аннотация

Рассматривается задача распределения множества заданий между устройствами однородной вычислительной системы по минимаксному критерию. Приводится постановка задачи, в которой подробно описываются объект исследования и принципы его функционирования. Для решения поставленной задачи предлагается использовать приближённые алгоритмы. Рассмотрены классический и модифицированный алгоритмы Крона и способы их улучшения за счёт формирования начального распределения заданий между устройствами вычислительной системы. С этой целью используются алгоритм критического пути и алгоритм Пашкеева. Для оценки эффективности полученных модификаций алгоритма Крона в работе приведены выходные значения ряда вычислительных экспериментов при различных входных параметрах. Эффективность модифицированных алгоритмов оценивалась по времени работы и отклонению полученного значения загрузки от оптимального значения. Разработаны программные средства для анализа эффективности модифицированных алгоритмов.