http://dx.doi.org/10.17213/0321-2653-2016-1-41-46
РАЗЛИЧНЫЕ ПОДХОДЫ К РЕШЕНИЮ ОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ ЭВРИСТИЧЕСКИМИ АЛГОРИТМАМИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, Донской государственный технический универсистет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Жуковский Александр Георгиевич – д-р пед. наук, профессор, Донской государственный технический универсистет, г. Ростов-на-Дону, Россия. E-mail: zhykovskij@mail.ru
Золотых Олег Анатольевич – доцент, Донской государственный технический универсистет, г. Ростов-на-Дону, Россия.
Ростов Адрей Николаевич – магистрант, Институт энергетики и машиностроения Донского государственного технического университета, г. Ростов-на-Дону, Россия.
Впервые предлагаются два новых метода решения однородной минимаксной задачи: модель Голдберга c использованием в начальной популяции элиты, получаемой на основе использования эвристического алгоритма Крона, и алгоритм Крона, где для формирования начального распределения используется модель Голдберга. Целью работы является сравнение по точности исходной модели Голдберга и алгоритма Крона, а также их модификаций, полученных в результате совмещения исходных алгоритмов. Так как алгоритмы и их модификации используют множество случайных параметров, аналитически невозможно определить, какой из них даст более точное решение, поэтому при исследовании алгоритмов и их модификаций проводились вычислительные эксперименты, позволившие сформировать выводы, характеризующие эффективность исследованных алгоритмов.
генетический алгоритм; однородная система; минимаксная задача; метод Крона; элитная особь; эвристический алгоритм.
[
1. Коффман Э.Г. Теория расписания и вычислительные машины. M.: Наука, 1987.
2. Алексеев В.Ю. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.
3. Кобак В.Г., Иванов М.С. Сравнительный анализ алгоритмов решения задачи планирования в однородных вычислительных системах // Математические методы в технике и технологиях - ММТТ-20: сб. тp. XX Междунар. науч. конф. Ярославль, 2007. Т. 2.
4. Кобак В.Г., Титов Д.В., Золотых О.А. Алгоритмический подход к увеличению эффективности алгоритма Крона в однородных системах // Материалы межвузовской науч.-техн. конф. «Перспективы развития средств и комплексов связи. Подготовка специалистов связи». Новочеркасск, 2011. С. 179 – 181.
5. Кобак В.Г., Титов Д.В., Золотых О.А. Повышение эффективности алгоритма Крона за счёт модификации начального распределения заданий // Труды XX междунар. науч.-техн. конф. «Современные проблемы информатизации». Воронеж, 2011. С. 234 – 239.
6. Кобак В.Г., Титов Д.В., Золотых О.А. Исследование алгоритма Крона и его модификации при различных исходных данных // Вестн. ДГТУ. 2012. № 8(69). С. 62 – 67.
7. Повышение эффективности генетического алгоритма на базе модели Голдберга за счет применения элиты / В.Г. Кобак, Д.В. Титов, О.А. Золотых, Д.В. Плешаков // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2014. № 3. С. 12 – 15.
8. Различные подходы для увеличения эффективности алгоритма Крона в однородных системах обработки информации / В.Г. Кобак, Д.В. Титов, О.А. Золотых, Д.В. Чижов // Электромеханика. 2012. № 5. С. 74 – 77.
9. Исследование эффективности генетических алгоритмов распределения для однородных систем при кратности заданий количеству устройств / В.Г. Кобак, Д.В. Титов, О.А. Золотых, В.И. Калюка // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2011. № 3. 19 – 22.
10. Кобак В.Г., Титов Д.В., Золотых О.А. Исследование алгоритма Крона при разных начальных условиях // Математические методы в технике и технологиях - ММТТ-24: сб. тр. Междунар. науч. конф. / СГТУ. Саратов, 2011. Т. 8.