148
правок
Изменения
→Доказательство корректности алгоритма
==Доказательство корректности алгоритма==
{{Теорема
|statement=
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Для доказательства оптимальности полученного расписания рассмотрим только первый случай. Второй доказывается аналогично.
Рассмотрим 3 последовательности выполнения работы, начиная с нулевого времени: все работы на первом станке, все работы на втором станке и первая работа на втором станке плюс последняя - на первом.<br/>
</ol>
Три последовательности выполнения работ, которые мы рассмотрели вначале, являются нижней оценкой для OpenShop problem, следовательно они и дают оптимальное решение.
}}
==Псевдокод==
