1679
правок
Изменения
→1 | prec | f_max
Дано множество работ <tex> J </tex> размера <tex> n </tex>, для которых заданы отношения предшествования, нужно минимизировать <tex> f_{max} = \max\limits_i f_i(C_i) </tex>, где <tex> f_i</tex> — монотонно неубывают по времени завершения работы <tex> i </tex>.
Приведем алгоритм(''Lawler's algorithm'') решения за <tex> O(n^2) </tex> и докажем его оптимальность:
# Пусть <tex> U \subseteq J </tex> — множество еще не назначенных работ. Пусть <tex> p(U) = \sum\limits_{i \in U} p_i </tex>.
# Назначим работу <tex> j \in U </tex>, у которой нет потомков в <tex> U </tex> и с минимальным значением <tex> f_j(p(U)) </tex> последней работой в <tex> U </tex>.
