ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2022; 4: 5-10
http://dx.doi.org/10.17213/1560-3644-2022-4-5-10
РЕАЛИЗАЦИЯ МОДИФИКАЦИЙ АЛГОРИТМА КРОНА ДЛЯ РЕШЕНИЯ МИНИМАКСНЫХ ЗАДАЧ С БЕСКОНЕЧНОСТЯМИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия, valera33305@mail.ru
Валадов Антон Сергеевич – студент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия.
Шевченко Вадим Вадимович – студент, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия.
Аннотация
Рассматривается решение распределительной задачи для однородных систем, содержащих бесконечности, с помощью различных модификаций алгоритма Крона. Распределительным называется класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить. Приводится описание каждой из оцениваемых модификаций алгоритма Крона. Для оценки их эффективности продемонстрированы результаты экспериментов при различных входных данных и сравнение полученных данных алгоритмами. Данные содержат в себе информацию о среднем значении, полученном в результате работы модификации, а также среднее время выполнения одной задачи. Описаны взаимодействия с бесконечностями для каждого предложенного авторами алгоритма. Разработаны программные средства для анализа эффективности данных алгоритмов.
Ключевые слова: алгоритм Крона, приближенные алгоритмы, минимаксная задача, минимаксные задачи с бесконечностями, алгоритмы распределения
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Коффман Э.Г. Теория расписаний и вычислительные машины. M.: Наука, 1984. 337 с.
2. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. М.: Радио и связь, 1983. 272 с.
3. Алексеев О.Т. Комплексное применение методов дискретной оптимизации М.: Наука, 1987.
4. Кобак В.Г, Жуковский А.Г., Золотых О.А., Ростов А.Н. Решение однородной минимаксной задачи различными модификациями алгоритма Крона // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 3. С. 3-8.
5. Кобак В.Г, Жуковский А.Г., Золотых О.А., Ростов А.Н. Различные подходы к решению однородной минимаксной задачи теории расписаний эвристическими алгоритмами // Изв. вузов. Сев.-Кавк. регион. Техн. науки. 2016. № 1. С. 41-46.
6. Кобак В.Г., Иванов М.С. Сравнительный анализ алгоритмов решения задачи планирования в однородных вычислительных системах // Математические методы в технике и технологиях – ММТТ-20: сб. тр. ХХ науч. конф. Ярославль: Изд-во ЯГТУ, 2007
7. Кобак В.Г., Титов Д.В., Золотых О.А. Исследование алгоритма Крона и его модификации при различных исходных данных // Вестн. ДГТУ. Вып. 8(69). Ростов н/Д., 2012.
8. Кобак В.Г, Титов Д.В., Золотых О.А., Чижов Д.В. Различные подходы для увеличения эффективности алгоритма Крона в однородных системах обработки информации // Электромеханика. 2012. № 5. С. 74-77.
9. Кобак, В.Г., Золотых О.А., Титов Д.В. Повышение эффективности алгоритма Крона за счёт модификации начального распределения заданий // Современные проблемы информатизации в моделировании и социальных технологиях: сб. тр. XVI Междунар. открытой науч. конф. Воронеж: Научная книга, 2011. С. 246-251.
10. Кобак В.Г., Титов Д.В., Золотых О.А. Исследование алгоритма Крона при разных начальных условиях // Математические методы в технике и технологиях – ММТТ-24: сб. тр. Междунар. науч. конф. / СГТУ. Саратов, 2011. Т. 8Mathematical methods in engineering and technologies - MMTT-24: sat. tr. International Scientific Conference. SSTU, 2011; (8).