1679
правок
Изменения
→O | p_ij = 1| Sum(U_i)
Действительно, если в допустимом расписании все периоды выполнения <tex> t_{iq} </tex> работы <tex> i </tex> заменить на периоды выполнения работы <tex> j > i </tex>, оно останется допустимым, так как <tex> t_{iq} \le d_i \le d_j </tex>.
}}
Таким образом, будем брать последние <tex> k </tex> работ и пытаться составить из них допустимое расписание (для этого известен полиномиальный алгоритмза <tex> O(mn) </tex><ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 163 </ref>). Получили решение за <tex> O(mn\log n \cdot T_{exists}(n)) </tex>, где <tex> T_{exists} </tex> — время решения задачи <tex> O \mid p_{ij}=1, d_i \mid - </tex>.
== Жадное построение расписания ==
