148
правок
Изменения
→Описание алгоритма
</ol>
[[Файл:O2Cmax.gif|300px|center]]
==Доказательство корректности алгоритма==
Для доказательства оптимальности полученного расписания рассмотрим только первый случай. Второй доказывается аналогично.
Рассмотрим 3 последовательности выполнения работы, начиная с нулевого времени: все работы на первом станке, все работы на втором станке и первая работа на втором станке плюс последняя - на первом.<br/>
Докажем, что время окончания одной из этих трёх последовательностей максимальное из всех возможных окончаний.<br/>
Пронумеруем работы в порядке выполнения их на первом станке и рассмотрим последовательность<br/>
<ul><tex>0 \rightarrow a_{1} \rightarrow \dots \rightarrow a_{i} \rightarrow b_{i} \rightarrow \dots \rightarrow b_{n-1}</tex></ul>
<ol>
<li>Если <tex>i \in I</tex>, то
<ul><tex>\sum \limits _{j = 1}^{i}a_{j} + \sum\limits_{j = i}^{n -1}b_{j} \le \sum\limits_{j = 1}^{i-1}b_{j} +a_{i}+ \sum\limits_{j = i}^{n -1}b_{j}</tex></ul>
Это неравенство получаем из первого случая и того, что <tex>i \in I \Rightarrow \ \forall j < i, j \in I \Rightarrow \forall j < i, a_{j} \le b_{j}</tex>
<ul><tex>\sum \limits_{j = 1}^{i-1}b_{j} +a_{i}+ \sum\limits_{j = i}^{n -1}b_{j} \le \sum \limits_{j = 1}^{n} b_{j}</tex></ul>
Это неравенство получено из того, что <tex>a_{i} \le a_{n} \le b_{n}</tex>, где <tex>n = x</tex>
</li>
<li>
Если <tex>i \in J</tex>, то
<ul><tex>\sum \limits _{j = 1}^{i}a_{j} + \sum\limits_{j = i}^{n -1}b_{j} \le \sum\limits_{j = 1}^{i}a_{j} +b_{i}+ \sum\limits_{j = i+1}^{n -1}a_{j}</tex></ul>
Это неравенство получаем из первого случая и того, что <tex>i \in J \Rightarrow \ \forall j > i, j \in I \Rightarrow \forall j > i, b_{j} \le a_{j}</tex>
<ul><tex>\sum \limits_{j = 1}^{i}a_{j} +b_{i}+ \sum\limits_{j = i+1}^{n -1}a_{j} \le \sum \limits_{j = 1}^{n} a_{j}</tex></ul>
Это неравенство получено из того, что <tex>b_{i} \le a_{i} \le a_{n}</tex>, где <tex>n = x</tex>
</li>
</ol>
Три последовательности выполнения работ, которые мы рассмотрели вначале, являются нижней оценкой для OpenShop problem, следовательно они и дают оптимальное решение.
==Псевдокод==
