Изменения

Перейти к: навигация, поиск

QpmtnCmax

Нет изменений в размере, 12:05, 23 июня 2012
Доказательство корректности алгоритма
В этом случае, если <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le i \le m-1 </tex>, Level последней работы выполнявшейся на станке <tex> M_i </tex> равен <tex> f_i - \varepsilon </tex>. Где <tex> \varepsilon > 0</tex> достаточно мал, и меньше чем <tex>Level</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию.
Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = ... = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex> необходимо начать их в момент времени 0. Так как если это не выполняется, то у нас найдется работа <tex> j_i J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает что в момент времени ноль, начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ, стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \ge p_2(0) \ge ... \ge p_m(0) \ge p_i(0) </tex>. Из чего следует, что <tex> p_1(T - \varepsilon) \ge ... \ge p_m(T - \varepsilon) \ge p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex> удовлетворяющего условию <tex> 0 \le \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Противоречие. Получаем <tex> T = P_j \over S_j </tex>.
==Пример==
Анонимный участник

Навигация