Изменения

Эта задача может быть решена сведением к решению [[Венгерский алгоритм решения задачи о назначениях {{Лемма| задачи о назначениях]].id=lemma1А именно, покажем, что решение задачи состоит |statement= Пусть все работы отсортированы в сопоставлении порядке неубывания дедлайнов <tex>nd_i</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе Тогда существует оптимальное расписание вида <tex>ii_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n </tex> время , где <tex>ti_1 < i_2 < \ldots < i_s </tex>{{---}} номера работ, то вклад в целевую функцию будет которые успеют выполниться вовремя, а <tex> f_i(t i_{s+ 1) }, \ldots, i_n </tex>{{---}} номера просроченных работ.|proof= Это можно показать следующим образом}}

  отсортиртировать работы по неубыванию времена появления времен дедлайнов <tex>r_id_i</tex>

'''for''' <tex> i t \in \{ 2 -p_{max} \ldots n -1 \} </tex> '''for''' <tex>t_ij \in \{ 0 \ldots n \} </tex> F_j(t) = \infty '''for''' <tex>t \in \max(r_i, t_{i-10 \ldots T \} + 1)</tex> F_0(t) = 0 Для того, чтобы найти оптимальное расписание, построим полный [[Основные_определения_теории_графов#Двудольный_граф |двудольный граф]], в котором будут доли '''for''' <tex>V_1 = j \left in \{ 1,0 \ldots,n \right\} и V_2 = </tex> '''for''' <tex> t \left in \{ t_1,0 \ldots,t_n \rightd_j \}</tex> и ребра '''if''' <tex>c_F_{ijj-1}+ w_j < F_{j-1}(t-p_j) </tex> между ними:'''then''' <tex> F_j(t) = F_{j-1}(t) + w_j <p/tex> '''else''' <tex>c_ F_j(t) = F_{ijj-1} =(t-p_j) </tex> '''for''' <tex> t \left in \{\begind_{array}{ll} f_i(t_j j+ 1), & r_i } \leqslant t_i ldots T \\\infty, & \mathrm{otherwise}\end{array} \right.</tex> <tex> F_j(t) = F_{j}(d_j) </ptex> Решив задачу о назначениях для данного графа, получим оптимальное расписание.