40
правок
Изменения
м
→Доказательство корректности алгоритма
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Чтобы доказать корректность, надо доказать, что на каждом станке никакая из работ в любой момент времени выполняется не пересекаетсяболее одной работы, и что каждая работа в каждый момент времени выполняется только не более, чем на одном станке.<br/>Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \ge \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке нет пересечения работв любой момент времени выполняется не более одной работы.<br/>Докажем теперь второе утверждение. У нас имеется 3 блокаработ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
<ol>
<li>Для блока <tex> \{x\}</tex> пересечения отсутствуют из того, что <tex> C_{max} \ge a_{x}+b_{x}</tex>, а этот блок выполняется с разных концов станков, значит он выполнения работы <tex> x </tex> на разных станках не может пересекатьсяпересекаются.</li><li>Для блока <tex> I \setminus \{x\}</tex> рассмотри рассмотрим сумму:
<ul><tex>\sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex></ul>
Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
