148
правок
Изменения
Нет описания правки
<ol>
<li>Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex></li>
<li>Найдем <tex>a_{x} = \max \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = \max \{b_{i} \mid i \in J\}</tex> </li>
<li> Рассмотрим 2 случая. Первый случай, когда <tex>a_{x} \ge b_{y}</tex>, тогда
<ul>
</li>
</ol>
==Псевдокод==
<tex>I \leftarrow \varnothing </tex>
<tex>J \leftarrow \varnothing </tex>
for <tex>i = 1 \dots n</tex>
if <tex>a_{i} \le b{i}</tex>
<tex> I \leftarrow I \cup \{i\} </tex>
else
<tex> J \leftarrow J \cup \{i\} </tex>
Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
if <tex>a_{x} < b_{y}</tex>
Поменять местами первый и второй станок
Пересчитать <tex>I, J, x</tex>
Запомнить, что поменяли
<tex>time1 \leftarrow 0</tex>
shed2[x] <tex>\leftarrow 0</tex>
<tex>time2 \leftarrow b_{x}</tex>
Для всех <tex>i \in I \setminus \{x\}</tex>
sched1[i] <tex>\leftarrow time1</tex>
<tex>time1 \leftarrow time1 + a_{i}</tex>
<tex>time2 \leftarrow \max\{time1, time2\}</tex>
sched2[i] <tex>\leftarrow time2</tex>
<tex>time2 \leftarrow time2 + b_{i}</tex>
Для всех <tex>i \in J</tex>
sched1[i] <tex>\leftarrow time1</tex>
<tex>time1 \leftarrow time1 + a_{i}</tex>
<tex>time2 \leftarrow \max\{time1, time2\}</tex>
sched2[i] <tex>\leftarrow time2</tex>
<tex>time2 \leftarrow time2 + b_{i}</tex>
<tex>time1 \leftarrow \max\{time1, b_{x}\}</tex>
sched1[x] <tex>\leftarrow time1</tex>
<tex>time1 \leftarrow time1 + a_{x}</tex>
<tex>C_{max} \leftarrow \max\{time1, time2\}</tex>
if станки меняли местами
поменять их обратно
