Объектом исследования является задача выполнимости булевых формул (SAT). Цель работы - исследование эффективности и улучшение эвристических методов решения задачи выполнимости булевых формул. В работе выполнен теоретический обзор методов решения задачи SAT. Проводилась экспериментальная проверка эвристических методов решения задачи выполнимости. В ходе исследования были предложены две модификации алгоритма вероятностного локального поиска. Степень внедрения – разработано программное приложение на основе вероятностного локального поиска. Эффективность предложенных модификаций подтверждается ускорением поиска решения на некоторых булевых формулах.