Изменения

|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>.

Данная ==Наивное решение==В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или, например, дробными, данная задача является NP-сложной задачейможет быть решена с помощью перебора.

Будем перебирать все перестановки чисел от <tex>1</tex> до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum \limits_{i=1}^n w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ. Данное решение будет работать за <tex> \mathcal{O}(n \cdot n!)</tex>. ==РешениеПеребор с битовыми масками==Применим Далее широко будет использоваться следующий факт: {{Лемма|id=lemma1|statement= Пусть все работы отсортированы в порядке неубывания дедлайнов <tex>d_i</tex>.Тогда существует оптимальное расписание вида <tex>i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n </tex>, такое, что <tex>i_1 < i_2 < \ldots < i_s </tex> {{---}} номера работ, которые успеют выполниться вовремя, а <tex>i_{s+1}, \ldots, i_n </tex> {{---}} номера просроченных работ.|proof= Пусть у нас есть некоторое оптимальное раписание <tex>S</tex>. Получим необходимое нам расписание путем переставления некоторых работ. #Если работа с номером <tex> i</tex> выполнится в <tex>S</tex> с опозданием, то переставим эту работу в конец. При этом, так как работа просрочна в оптимальном расписании <tex>S</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>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>\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 + 1</tex> '''to''' <tex>TL</tex> <tex> F_j(t) = F_{j}(d_j) </tex> Для тогоСогласно лемме, чтобы найти само расписание, по доказанной ниже лемме, нам достаточно найти множество будет состоять из работ, которые будут выполнены с опозданием. Это может быть сделано следующим способом: t = d_n L = \varnothing '''for''' не попавших в <tex>j = nL</tex> '''downto''' <tex>1</tex> <tex>t = \min(t, d_j)отсортированных по неубыванию </tex> '''if''' <tex> F_j(t) = F_{j-1}(t) + w_j d_i</tex> и работ из <tex> L = L \cup \{j\} </tex> </tex> '''else''' <tex> t = t - p_j </tex>, записанных в конец в любом порядке.

==Доказательство корректности и оптимальности=Время работы= {{Лемма|id=lemma1|statement= Пусть все работы отсортированы в порядке неубывания дедлайнов <tex>d_i</tex>.Тогда существует оптимальное расписание вида В функции <tex>i_1, i_2, \ldots, i_s, i_mathrm{s+1getAnswer}, \ldots, i_n </tex>, такое, что пересчет динамики происходит за <tex>i_1 < i_2 < \ldots < i_s mathcal{O}(n T)</tex> {{---}} номера работ, которые успеют выполниться вовремя, а функция <tex>i_\mathrm{s+1getLate}, \ldots, i_n </tex> {{---}} номера восстанавливает список просроченных работ.|proof= Пусть у нас есть некоторое оптимальное раписание за <tex>S\mathcal{O}(n)</tex>. Получим необходимое нам расписание путем переставления некоторых работ. #Если работа с номером <tex> i</tex> выполнится Дальнейшее восстановление расписания происходит в худшем случае за <tex>S\mathcal{O}(n \log n)</tex> с опозданием, то переставим эту работу в конец. При этомОтсюда видно, так как работа просрочна в оптимальном расписании <tex>S</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>S</tex>, как оптимального решения.#*Поскольку <tex>d_i < d_j </tex> и работа <tex>i</tex> будет заканчиваться на <tex>p_j</tex> единиц времени раньше, то стоящая сразу послее нее работа <tex>j</tex> тоже будет успевать выполниться.}}==Время работы== Время работы приведенного выше алгоритма {{---}} <tex>\mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.