Эвристические и вероятностные методы

Неудовлетворительное состояние развития точных методов решения задач ТР обусловило разработку приближенных методов, позволяющих получать приемлемые решения при сравнительно небольших затратах времени и средств. Условно приближенные методы делятся на эвристические и вероятностные.

Эвристические алгоритмы основаны на приеме, который называется приемом снижения требований. Он заключается в отказе от поиска оптимального решения за приемлемое время. Эвристические алгоритмы используют различные разумные соображения без строгих обоснований.

Широко применяется так называемый метод локального поиска. При этом заранее выбранное множество перестановок используется для последовательного улучшения начального решения до тех пор, пока такое улучшение возможно, в противном случае оказывается достигнутым локальный оптимум.

Еще одно из направлений эвристических методов решения задач ТР состоит в формировании правил или функций предпочтения (приоритетов). Для каждой i-й работы из множества ожидающих выполнения работ, вычисляется значение функции предпочтения и выбирается та работа, для которой достигает максимума или минимума.

Примеры правил предпочтения:

1) Правило SPT (shirtest processing time). Предпочтение отдается той работе (операции) из множества готовых к обработке на освободившейся машине, у которой время выполнения на этой машине минимально.

2) Правило LRT (longest remaining time). Требует выбора напряженной работы, т.е. той, у которой сумма времен выполнения оставшихся операций наибольшее.

3) Правило LPT (longest processing time). Предпочтение отдается той работе (операции) из множества готовых к обработке на освободившейся машине, у которой время выполнения на этой машине максимально.

Достоинством эвристических методов является удобство реализации их на ЭВМ даже при решении громоздких задач.

Недостатки эвристических методов заключаются в сложности оценки близости полученных расписаний к оптимальному. Кроме того для каждой функции предпочтения существуют задачи, для которых применение данной функции приводит к плохим результатам. Один из путей совершенствования метода функций предпочтения состоит в их привязке к классам задач.

Вероятностные методы связаны с k-кратным моделированием расписаний. Выбор работ из множества ожидающих выполнения осуществляется случайным образом. После k-кратного проигрывания выбирается наилучшее расписание, которое принимается за решение задачи. При этом различают:

а) ненаправленный случайный поиск;

б) направленный случайный поиск без самообучением;

в) направленный случайный поиск с самообучением.