90
правок
Изменения
→Доказательство корректности алгоритма
Предположим обратное, что не существует оптимального расписания с одиннаковыми перестановками работ на станках. Рассмотрим некоторое оптимальное расписание с максимальным по длине общим префиксом на станках.
Пусть его длина равна <tex> k </tex>, где <tex> k < n </tex>. Пусть на <tex> k </tex> позиций на первом и втором станках стоит работа <tex> i </tex>, а на втором станке на позиций <tex> k + 1 </tex> стоит работа <tex> j </tex>. Тогда заметим, что если мы поставим работу <tex> j </tex> на первом станке сразу после работы <tex> i </tex>, то последовательные работы с <tex> h </tex> по <tex> m </tex> (см. Рис. 1) по-прежнему будут успевать выполниться, так как на втором станке они выполняются в текущем расписаний после <tex> j </tex>. Таким образом нам удалось увеличить длину наибольщего общего префикса, а так как по нашему предположению она была максимальна, то наше предположение неверно, то искомое расписание с одиннаковым порядком выполнения работ на обоих станках существует.
}}
