Изменения

|definition= Есть один станок и <tex>n</tex> работ. Для каждой работы заданы время выполнения <tex> p_i,</tex> дедлаин дедлайн <tex>d_i</tex> и стоимось стоимость выполнения этой работы <tex>w_i \geqslant 0</tex>.Необходим Необходимо минимизировать <tex>\sum w_i U_i</tex>.

Данная задача является NP-сложной задачей.==Общее Наивное решение==В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или , например, дробными, данная задача может быть решена с помощью перебора. Будем перебирать все перестановки чисел от <tex>1</tex> до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum \limits_{i=1}^n w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ. Данное решение будет работать за <tex> \mathcal{O}(n \cdot n!)</tex>. ==Перебор с битовыми масками== Далее будем пользоваться следующим фактомшироко будет использоваться следующий факт:

#Если работы с номерами <tex>i</tex> и <tex>j</tex> в расписании <tex>S</tex> выполняются вовремя, но при этом <tex>d_i < d_j </tex>, но и <tex>j</tex> стоит в <tex>S</tex> раньше <tex>i</tex>. Тогда , то переставим работу с номером <tex>j</tex> так, чтобы она выполнялась после работы <tex>i</tex>. Таким образом, каждая из работ, находившихся в <tex>S</tex> между <tex>j</tex> и <tex>i</tex>, включая <tex>i</tex>, будет выполняться в новом расписании на <tex>p_j</tex> единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:

#*Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие в с исходным выбором <tex>S</tex>, как оптимального решения.#*Поскольку <tex>d_i < d_j </tex> и работа <tex>i</tex> будет заканчиваться на <tex>p_j</tex> единиц времени раньше, то стоящая сразу послее после нее работа <tex>j</tex> тоже будет успевать выполниться.

Перебираем все битовые маскиНаше решение будет построено на переборе всех битовых масок. Для каждой маски При построении решения мы будем считать, что если опираться на доказанную лемму.  Если бит, соответствующий заданию с номером <tex>i</tex> равен <tex>1</tex>, то будем предполагать, что это задание успеет должно быть записано в список заданий, которые, возможно, успеют выполниться, если бит равен <tex>0</tex> {{---}} то не успеет.Далее, согласно доказанной лемме, мы должны выписать все сортируем заданияиз этого списка по времени неубывания дедлайнов, которыеа те задания, согласно нашему предположениючто не попали в этот список, могут должны быть выполнены без опоздания в начало расписания в порядке возрастания дедлайнов <tex>d_i</tex>, а оставшиеся записать отправлены в конец расписания в любом порядке.Далее проверяем полученное возможное расписание на корректность, и , в случае успеха, обновляем ответ. Перебор всех масок может быть произведен за <tex>\mathcal{O}(2 ^ n)</tex>, и <tex>\mathcal{O}(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>\mathcal{O}(n \cdot 2^n)</tex>.

Применим В ситуации, когда времена выполнения работ <tex>p_i</tex> целочисленные, а значение <tex> \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_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>. * За <tex>p_{max}</tex> обозначим самое большое из времен выполнения заданий.* Значения <tex> F_j(t)</tex> будем хранить в массиве <tex>F[j][t]</tex>.* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в <tex>d[i] </tex> {{---}} дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения. '''function''' <tex> \mathrm{getAnswer}(p : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> w : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> d : </tex> '''int'''<tex>\mathbf{[n]} ):</tex> '''int''' '''int''' <tex>T = 0 </tex> '''for''' <tex>i = 1 .. n</tex> <tex>T = T + p[i]</tex> '''int''' <tex>F[][]</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][t] = \infty</tex> '''for''' <tex>t = 0</tex> '''to''' <tex>T</tex> <tex>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[j-1][t] + w[j] < F[j-1][t-p[j]] </tex> <tex> F[j][t] = F[j-1][t] + w[j] </tex> '''else''' <tex> F[j][t] = F[j-1][t-p[j]] </tex> '''for''' <tex>t = d[j] + 1</tex> '''to''' <tex>T</tex> <tex> F[j][t] = F[j][d[j]] </tex> '''return''' <tex> F[n][d[n]] </tex>

сортируем работы Для того, чтобы найти само расписание, по неубыванию времен дедлайнов доказанной выше лемме, нам достаточно найти множество работ <tex>d_iL</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом: '''function''' <tex>t_1</tex> = <tex>r_1\mathrm{getLate}(F : </tex> '''forint''' <tex>t = -\mathbf{[n][p_{max}]},</tex> <tex> p : </tex> '''toint''' <tex>-1\mathbf{[n]},</tex> '''for''' <tex>j = 0w : </tex> '''toint''' <tex>\mathbf{[n]},</tex> F_j(t) = \infty '''for''' <tex>t = 0d : </tex> '''toint''' <tex>T\mathbf{[n]} ):</tex>'''set<int>''' F_0(t) = 0 '''forint''' <tex>j t = 1d[n]</tex> '''toset<int>''' <tex>nL = \varnothing</tex> '''for''' <tex>t j = 0n</tex> '''todownto''' <tex>d_j1</tex> <tex>t = \min(t, d[j])</tex> '''if''' <tex> F_{F[j][t] = F[j-1}(][t) ] + w_j < F_{w[j-1}(t-p_j) ] </tex> <tex> F_j(t) L = F_L \cup \{j-1\}(t) + w_j </tex>

<tex> F_j(t) = F_{j-1}(t-p_j) p[j] </tex> '''forreturn''' <tex>t = d_j + 1L</tex>Согласно лемме, само расписание будет состоять из работ, не попавших в <tex>L</tex> '''to''' , отсортированных по неубыванию <tex>Td_i</tex> и работ из <tex> F_j(t) = F_{j}(d_j) L</tex>, записанных в конец в любом порядке.

Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом: t = d_n L = \varnothing=Время работы=== '''for''' В функции <tex>j = n\mathrm{getAnswer}</tex> '''downto''' пересчет динамики происходит за <tex>1\mathcal{O}(n T)</tex> , а функция <tex>t = \min(t, d_j)mathrm{getLate}</tex> '''if''' восстанавливает список просроченных работ за <tex> F_j(t) = F_\mathcal{j-1O}(tn) + w_j </tex> . Дальнейшее восстановление расписания происходит в худшем случае за <tex> L = L \cup \mathcal{jO}(n \} log n)</tex> </tex> '''else''' <tex> t = t - p_j </tex> ==Время работы== Время . Отсюда видно, что время работы приведенного выше алгоритма {{---}} <tex>\mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.