148
правок
Изменения
→Доказательство корректности алгоритма
<li>Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
<ul><tex>\sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex></ul>,
где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br/br>
Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li>
<li>Покажем, что любая работа из <tex>J</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
<ul><tex>\sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex></ul>,где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br/>
Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li>
