Методы решения задач теории расписаний

Рассмотрим основные методы решения задач теории расписаний, которые могут строиться на различных принципах.

Как уже отмечалось, в настоящее время не существует регулярных алгоритмов решения задач теории расписаний (кроме задачи Джонсона), которые бы гарантировали получение оптимального решения.

В общем случае задачи теории расписаний относятся к NP-полным задачам. Для получения точного решения таких задач следует произвести полный перебор всех возможных вариантов. Однако количество таких вариантов обычно оказывается чрезвычайно большим и получение решения задач теории расписаний, встречающихся в реальных условиях производства, с помощью полного перебора всех возможных вариантов потребует недопустимо большого времени расчетов. Так, например, для получения оптимального расписания в одной из простейших задач, связанных с обработкой  деталей на  станках, теоретически может возникнуть потребность в построении и выборе лучшего из  вариантов расписаний обработки этих деталей, что при реальных значениях  и  для современных производств может потребовать не один год на выполнение такого перебора.

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