В данной работе рассматривается моделирование производственного расписания с учетом затрат на переналадку оборудования в виде ориентированного графа. Поиск оптимального расписания в таком случае сводится к поиску кратчайшего гамильтонова цикла. Была произведена адаптация известного метода локального поиска для решения данной задачи. Эксперимент показал применимость и эффективность данного метода.