Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail
Обратим внимание, что оптимальное решение задачи == <tex>F_2 \mid pmtn \mid C_{max}</tex> == Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex> , приведённой выше. Докажем это. Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение <tex>C_{max}</tex> . Рассмотрим первую машину. Допустим, что некоторая работа J выполняется в 2 разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в том момент, когда мы начинается второй промежуток. Таким образом работа J станет выполняться без прерывания. При этом работы, которые были между промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа J может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а остальные работы были сдвинуты влево, наложений точно не возникнет.Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Расписание останется корректным по аналогичным причинам. Повторим операцию. Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex> , так как мы только меняли порядок выполнения работ, что и требовалось доказать.
