Рассмотрена задача составления расписания ремонтов локомотивов в пунктах технического обслуживания локомотивов (ПТОЛ). Для каждого локомотива известно время движения до каждого ПТОЛ, степень его важности и время ремонта. Для каждого ПТОЛ задана его удельная производительность по ремонту локомотивов. Каждый ПТОЛ может обслужить любой локомотив. Составлена целевая функция задачи, характеризующая время обслуживания всех локомотивов. Применен эвристический алгоритм локального поиска, минимизирующий время обслуживания всех локомотивов, в котором рассматриваются всевозможные перестановки пар локомотивов в расписании, уменьшающие целевую функцию, и выбирается одна из них согласно введенному параметру. Исследуется зависимость значения целевой функции задачи от параметра выбора перестановки при реализации алгоритма локального поиска. Проведено сравнение суммарных значений целевых функций расписаний, построенных с помощью «жадного» алгоритма и алгоритма локального поиска. С помощью реализации рассмотренных алгоритмов на языке С++ построено расписание обслуживания локомотивов на ПТОЛ и найдено значение суммарной целевой функции в задаче с псевдореальными данными