Изменения

Перейти к: навигация, поиск

O2Cmax

81 байт добавлено, 23:48, 16 мая 2016
м
Описание алгоритма
##*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.
##*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex>.[[Файл:Picture2.gif‎|500px|center]]
## <tex>a_{x} \leqslant b_{y}</tex>. Сводится к первому, если поменять местами станкии соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.
==Доказательство корректности алгоритма==
251
правка

Навигация