Просмотр исходного текста страницы J2ni2Cmax

==Постановка задачи==
Рассмотрим задачу:
<ol>
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
<li>Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. <tex>1</tex>.</li>
<li>Длина любой последовательности <tex><=2</tex>.
</ol>
Требуется минимизировать время окончания выполнения всех работ.

==Описание алгоритма==
<tex>M1</tex> - первый станок. <tex>M2</tex> - второй станок. 

Разобьем все работы на четыре множества:
<ol>
<li><tex>I1</tex> - множество всех работ, которые должны выполнится только на <tex>M1</tex>. </li>
<li><tex>I2</tex> - множество всех работ, которые должны выполнится только на <tex>M2</tex>. </li>
<li><tex>I12</tex> - множество всех работ, которые должны выполнится сначала на <tex>M1</tex> затем на <tex>M2</tex>. </li>
<li><tex>I21</tex> - множество всех работ, которые должны выполнится сначала на <tex>M2</tex> затем на <tex>M1</tex>. </li>
</ol>
Решим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I12</tex> и для <tex>I21</tex>. Получим расписание <tex>S12</tex> и <tex>S21</tex>.
Тогда оптимальное расписание для нашей задачи будет следующим:
<ol>
<li>Расписание <tex>M1</tex>: <tex>I12</tex> в соответсвии с расписанием <tex>S12</tex>. <tex>I1</tex> в произвольном порядке. Затем <tex>I21</tex> в соответсвии с <tex>S21</tex>. </li>
<li>Расписание <tex>M2</tex>:<tex>I21</tex> в соответсвии с расписанием <tex>S21</tex>. Затем <tex>I2</tex> в произвольном порядке. Затем <tex>I12</tex> в соответсвии с <tex>S12</tex>. </li>
</ol>

==Доказательство корректности алгоритма==
{{Теорема
|statement=
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
|proof=
Доказательство будем вести от противного.<br/>
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания  различаются. Пусть в этот момент времени  в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на 
<ul><tex>t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})</tex></ul>
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
}}

==Псевдокод==
   <tex> S \leftarrow \{1 \dots n\}</tex>
   <tex> time \leftarrow 0</tex>
   <tex> answer \leftarrow 0</tex>
   while <tex> S \neq \varnothing </tex>
      <tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
      if <tex>j \neq null </tex>
         <tex> S \leftarrow S \setminus j</tex>
         <tex> Answer \leftarrow Answer + time \cdot w_{j}</tex>
      <tex> time++</tex>

==Сложность алгоритма==
Время работы алгоритма равно времени работы алгоритма  [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]].

Сложность алгоритма <tex>O(n\log n)</tex>.

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]