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