1679
правок
Изменения
→Сведение к другой задаче
== Сведение к другой задаче ==
При сведении текущей задачи теории расписаний <tex> S </tex> к какой-то другой <tex> S' </tex> (не обязательно задаче теории расписаний) необходимо доказать два пункта:# Допустимость расписания, построенного с помощью задачи <tex> P S' </tex>, или существование способа его трансформации в допустимоебез нарушения оптимальности.
# Следствие того, что если мы оптимизируем <tex> S' </tex>, мы также оптимизируем ответ для <tex> S </tex> (обратное в общем случае неверно).
Примечание — если требуется полиномиальное время для решения задачи, требуется, чтобы сведение к другой задаче и трансформация расписания в допустимое также происходили за полиномиальное время.
==== O | p_ij=1 | Sum(C_i) ====
== Построение расписания по нижней оценке ==
