Согласно требованиям РЖД, каждый локомотив должен проходить техническое обслуживание (ТО-2) в Пункте Технического Обслуживания Локомотивов (ПТОЛ) через установленный промежуток времени после предыдущего обслуживания. Объем локомотивного парка РЖД таков, что в среднем за сутки через ПТОЛ проходит от 50 до 100 локомотивов. По прибытии локомотива в ПТОЛ для прохождения ТО-2 может не оказаться доступных ремонтных позиций и локомотиву придется ждать своей очереди на обслуживание. В силу того, что каждый локомотив и ПТОЛ характеризуется определенными параметрами (серия, количество секций, количество доступных ремонтных позиций и др.) возникает задача планирования работы ПТОЛ. В работе описаны алгоритмы составления расписания технического обслуживания локомотивов в депо. Представлены алгоритм локального поиска и эвристический алгоритм. Представленная постановка задачи соответствует работе Восточного полигона РЖД. Для проверки работоспособности были проведены численные эксперименты и проведено сравнение представленных алгоритмов с оптимизатором IBM ILOG CPLEX. Предложенные алгоритмы были протестированы на реальных данных для существующих конфигураций ПТОЛ Восточного полигона Российских железных дорог.