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

Комбинаторный подход

Сводится к целенаправленной перестановке пар работ в некоторой исходной последовательности, пока не будет получено оптимальное nln близкое к оптимальному решение.

Вспомним сначала определения таких понятиях, как задачи класса Р, эффективные алгоритмы и NP -полные задачи.

Под «эффективным алгоритмом» понимается алгоритм, для которого число требуемых шагов растет как полином от размера входной задачи. Задачи, имеющие эффективные (полиномиальные) алгоритмы решения, принадлежат классу Р -задач.

Класс NP -задач обладает следующими свойствами:

- никакую NP -полную задачу нельзя решить никакими известными полиномиальными алгоритмами;

- если существует полиномиальный алгоритм для какой-нибудь NP -полной задачи, то существуют полиномиальные алгоритмы для всех NP -полных задач.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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