Изменения
→P | pmtn | C_max
# В допустимом расписании выполнение всех работ не может завершиться раньше одной из них, поэтому <tex> C_{max} \geqslant p_i </tex>.
# Если все станки работали время <tex> C_{max} </tex>, на них могло выполниться не больше <tex> C_{max} \cdot m </tex> работы, то есть <tex> \sum\limits_{i=1}^n p_i \leqslant C_{max} \cdot m </tex> и <tex> C_{max} \geqslant \dfrac1m \sum\limits_{i=1}^n p_i </tex>.
Из этих ограничений следует, что <tex> C_{max} = \max {\left( \max\limits_{i=1 \hdots n} p_i,~ \dfrac1m \sum\limits_{i=1}^n p_i \right)} </tex>.
Построим расписание, подходящее под эту границу: будем по очереди заполнять машины работами в произвольном порядке, и если очередная работа не помещается на текущей машине полностью, перенесем ее выходящую за <tex> C_{max} </tex> часть на следующую машину. Благодаря первому ограничению никакая работа не будет выполняться одновременно на двух станках, а благодаря второму — не останется работы, которую мы не сможем выполнить.
