УДК 681.3+681.5 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ РАСПРЕДЕЛЕНИЯ ДЛЯ ОДНОРОДНЫХ СИСТЕМ ПРИ КРАТНОСТИ ЗАДАНИЙ КОЛИЧЕСТВУ УСТРОЙСТВ 2011 г. В.Г. Кобак*, Д.В. Титов*, В.И. Калюка**, О.А. Золотых* *Донской государственный технический университет, г. Ростов-на-Дону **Филиал Военной академии связи, г. Новочеркасск *Donskoy State Technical University, Rostov-on-Don **Branch of the Military Academy of Communications (Novocherkassk) Представлена оценка двух модификаций генетического алгоритма, которые дают решения, очень близкие к оптимальным, за полиномиальное время. <...> Оба эти алгоритма приводят, в конечном счете, к решению двухприборной минимаксной задачи, однако по различным вычислительным путям. <...> Ключевые слова: теория расписаний; задача планирования; трудоемкость решения; генетический алгоритм; списочные алгоритмы; вычислительный эксперимент; множество заданий; ядра процессора. <...> Для упорядочивания и распределения независимых заданий по параллельно работающим независимым процессорам возникает необходимость в эффективном планировании. <...> Построение оптимального плана (расписания) относится к задачам NP-полным, т.е. трудоемкость решения распределительной задачи определяется по экспоненте, как ( ),mO n где O – временная асимптотическая сложность алгоритма, а n и m – целые числа больше единицы, задающие размерность задачи. <...> Исследование задач теории расписаний помогает изучить фундаментальные свойства практических задач и направлено на построение более эффективных алгоритмов решения. <...> Исследование методов построения расписаний, близких к оптимальным расписаниям, определяется возможностью экономии вычислительных ресурсов и времени на получение решения распределительной задачи. <...> Постановка задачи Задача теории расписаний для однородных систем обработки информации может быть сформулирована следующим образом. <...> Имеется однородная вычислительная система, состоящая из n идентичных устройств (параллельных процессоров или ядер процессора) P <...>