На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

В Институте компьютерных технологий и информационной безопасности Южного федерального университета предложено решение однородной распределительной задачи

12.07.2017

В области теории расписаний самым распространенным направлением является исследование классических однородных распределительных задач. Такие задачи часто применяются в различных сферах человеческой деятельности, например там, где необходимо эффективно выполнить организацию и планирование каких-либо работ, различных заданий и требований. В общем случае имеем какое-то количество работ и какое-то количество исполнителей. Выполнение любым работником какой-либо (но только одной) работы происходит с разными (неодинаковыми) затратами. Необходимо распределить работы таким образом, чтобы обойтись минимальными затратами. Примером распределительной задачи является задача составления плана выполнения комплекса программ в многопроцессорных вычислительных системах. Она является минимаксной однородной распределительной задачей теории расписаний. Поскольку распределительная задача относится к классу NP-полных, разработка новых, более эффективных методов, используемых для их решения, является актуальной проблемой теории расписаний. Зарубежными и российскими учеными разработано множество алгоритмов и методов, отличающихся как эксплуатационными свойствами, так и областью применения и решающих однородные распределительные задачи. Все методы решения однородных распределительные задач делятся на две группы – приближенные и точные. Самыми известными и наиболее эффективными из методов точного решения распределительной задачи являются алгоритмы, в основе которых лежат принципы метода ветвей и границ. Однако следует отметить, что эти алгоритмы имеют свойство экспоненциального роста сложности искомого решения относительно размерности распределительной задачи. Это особенно заметно, когда распределяемые в задаче задания характеризуются небольшой вариацией значений их размеров. Главная особенность метода ветвей и границ состоит в том, что обязательно возникнет такой пример, при решении которого необходим полный перебор. Поэтому для задач повышенной размерности возникнут большие временные затраты, хотя комбинаторная сложность уменьшится.
Подробное описание дается в статье «Однородная распределительная задача на основе моделей адаптивного поведения муравьиной колонии», авторы: Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. (Институт компьютерных технологий и информационной безопасности Южного федерального университета, г. Таганрог).