Изменения
Нет описания правки
==Псевдополиномиальное решение==
В ситуации, когда времена выполнения работ <tex>p_i</tex> целочисленные, а Применим значение <tex> \sum\limits_{i=1}^n p_i </tex> не очень большое, то для решения данной задачи можно применить [[Динамическое программирование|динамическое программирование]].
===Идея алгоритма===
Обозначим <tex>T = \sum\limits_{i=1}^n p_i</tex>.
Для всех <tex>t = 0, 1, \ldots, T </tex> и <tex>j = 1, \ldots, n</tex> будем рассчитывать <tex>F_j(t)</tex> {{---}} значение целевой функции <tex>\sum w_i U_i</tex>, при условии, что были рассмотрены первые <tex>j</tex> работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени <tex>t</tex>.
Ответом на задачу будет <tex>F_n(d_n)</tex>.
===Псевдокод===
Приведенный ниже алгоритм вычисляет <tex>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. * За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.* Считаем, что <tex>T = \sum\limits_{i=1}^n p_i</tex>.* Значения <tex> F_j(t)</tex> будем хранить в массиве <tex>F[j][t]</tex>.
сортируем работы по неубыванию времен дедлайнов <tex>d_i</tex>
'''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
'''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
<tex>F_j(F[j][t) ] = \infty</tex>
'''for''' <tex>t = 0</tex> '''to''' <tex>T</tex>
<tex>F_0(F[0][t) ] = 0</tex>
'''for''' <tex>j = 1</tex> '''to''' <tex>n</tex>
'''for''' <tex>t = 0</tex> '''to''' <tex>d_j</tex>
'''if''' <tex> F_{F[j-1}(][t) ] + w_j < F_{F[j-1}(][t-p_j) ] </tex> <tex> F_j(F[j][t) ] = F_{F[j-1}(][t) ] + w_j </tex>
'''else'''
<tex> F_j(F[j][t) ] = F_{F[j-1}(][t-p_j) ] </tex>
'''for''' <tex>t = d_j + 1</tex> '''to''' <tex>T</tex>
<tex> F_j(F[j][t) ] = F_{F[j}(][d_j) ] </tex>
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
'''for''' <tex>j = n</tex> '''downto''' <tex>1</tex>
<tex>t = \min(t, d_j)</tex>
'''if''' <tex> F_j(F[j][t) ] = F_{F[j-1}(][t) ] + w_j </tex>
<tex> L = L \cup \{j\} </tex> </tex>
'''else'''
<tex> t = t - p_j </tex>
===Время работы===
Время работы приведенного выше алгоритма {{---}} <tex>O\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
==См. также ==
== Источники информации ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
