1sumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 2 участников)
Строка 9: Строка 9:
 
В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.
 
В общем случае, когда времена выполнения работ <tex>p_i</tex> могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.
  
Будем перебирать все перестановки чисел от <tex>1</tex>  до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.
+
Будем перебирать все перестановки чисел от <tex>1</tex>  до <tex>n</tex>, обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение <tex>\sum \limits_{i=1}^n w_i U_i</tex>, полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.
  
Данное решение будет работать за <tex>O(n \cdot n!)</tex>.
+
Данное решение будет работать за <tex> \mathcal{O}(n \cdot n!)</tex>.
  
 
==Перебор с битовыми масками==
 
==Перебор с битовыми масками==
Строка 34: Строка 34:
 
Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке.
 
Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке.
 
Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.
 
Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.
Перебор всех масок может быть произведен за <tex>O(2 ^ n)</tex>, и <tex>O(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>O(n \cdot 2^n)</tex>.
+
 
 +
Перебор всех масок может быть произведен за <tex>\mathcal{O}(2 ^ n)</tex>, и <tex>\mathcal{O}(n)</tex> на пересчет ответа. Таким образом, это решение будет работать за <tex>\mathcal{O}(n \cdot 2^n)</tex>.
  
 
==Псевдополиномиальное решение==
 
==Псевдополиномиальное решение==
Строка 40: Строка 41:
 
В ситуации, когда времена выполнения работ <tex>p_i</tex> целочисленные, а значение <tex> \sum\limits_{i=1}^n p_i </tex> не очень большое, то для решения данной задачи можно применить [[Динамическое программирование|динамическое программирование]].
 
В ситуации, когда времена выполнения работ <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 = \sum\limits_{i=1}^n p_i</tex>.
Строка 59: Строка 60:
  
 
Ответом на задачу будет <tex>F_n(d_n)</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>F_j(t)</tex> для <tex>j = 0,\ldots, n </tex> и <tex>t = 0,\ldots, d_j </tex>.
Строка 65: Строка 67:
 
* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в  <tex>d[i] </tex> {{---}}  дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения.
 
* В массиве <tex>w[i] </tex> хранятся стоимости выполнения работ, в  <tex>d[i] </tex> {{---}}  дедлайны, а в <tex>p[i] </tex> {{---}} продолжительности выполнения.
 
    
 
    
   '''function''' <tex> getAnswer(p : </tex> '''int''' <tex>[n],</tex> <tex> w : </tex> '''int''' <tex>[n],</tex> <tex> d : </tex> '''int''' <tex>[n] ):</tex> '''int'''
+
   '''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>
 
     '''int''' <tex>T = 0 </tex>
 
     '''for''' <tex>i = 1 .. n</tex>
 
     '''for''' <tex>i = 1 .. n</tex>
 
       <tex>T = T + p[i]</tex>
 
       <tex>T = T + p[i]</tex>
 
     '''int''' <tex>F[][]</tex>
 
     '''int''' <tex>F[][]</tex>
     сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex>;
+
     сортируем работы по неубыванию времен дедлайнов <tex>d[i]</tex>
 
     '''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
 
     '''for''' <tex>t = -p_{max}</tex> '''to''' <tex>-1</tex>
 
       '''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
 
       '''for''' <tex>j = 0</tex> '''to''' <tex>n</tex>
Строка 87: Строка 89:
  
 
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ <tex>L</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
 
Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ <tex>L</tex>, которые будут выполнены с опозданием. Это может быть сделано следующим способом:
   '''function''' <tex> getSchedule(F : </tex> '''int''' <tex>[n][p_{max}],</tex> <tex> p : </tex> '''int''' <tex>[n],</tex> <tex> w : </tex> '''int''' <tex>[n],</tex> <tex> d : </tex> '''int''' <tex>[n] ):</tex> '''set<int>'''
+
   '''function''' <tex> \mathrm{getLate}(F : </tex> '''int'''<tex>\mathbf{[n][p_{max}]},</tex> <tex> p : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> w : </tex> '''int'''<tex>\mathbf{[n]},</tex> <tex> d : </tex> '''int'''<tex>\mathbf{[n]} ):</tex> '''set<int>'''
 
     '''int''' <tex>t = d[n]</tex>
 
     '''int''' <tex>t = d[n]</tex>
 
     '''set<int>''' <tex>L = \varnothing</tex>
 
     '''set<int>''' <tex>L = \varnothing</tex>
Строка 97: Строка 99:
 
         <tex> t = t - p[j] </tex>
 
         <tex> t = t - p[j] </tex>
 
     '''return''' <tex>L</tex>
 
     '''return''' <tex>L</tex>
 +
Согласно лемме, само расписание будет состоять из работ, не попавших в <tex>L</tex>, отсортированных по неубыванию <tex>d_i</tex>  и работ из <tex>L</tex>, записанных в конец в любом порядке.
  
 
===Время работы===
 
===Время работы===
Время работы приведенного выше алгоритма {{---}} <tex>O\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
+
В функции <tex>\mathrm{getAnswer}</tex> пересчет динамики происходит за <tex> \mathcal{O}(n T)</tex>, а функция <tex>\mathrm{getLate}</tex> восстанавливает список просроченных работ за <tex> \mathcal{O}(n)</tex>. Дальнейшее восстановление расписания происходит в худшем случае за <tex> \mathcal{O}(n \log n)</tex>. Отсюда видно, что время работы приведенного выше алгоритма {{---}} <tex> \mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)</tex>.
  
 
==См. также ==
 
==См. также ==
Строка 110: Строка 113:
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
 
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28
  
[[Категория: Дискретная математика и алгоритмы]]
+
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:17, 4 сентября 2022

[math]1 \mid\mid \sum w_i U_i[/math]


Задача:
Есть один станок и [math]n[/math] работ. Для каждой работы заданы время выполнения [math] p_i,[/math] дедлайн [math]d_i[/math] и стоимость выполнения этой работы [math]w_i \geqslant 0[/math]. Необходимо минимизировать [math]\sum w_i U_i[/math].


Наивное решение

В общем случае, когда времена выполнения работ [math]p_i[/math] могут быть сколь угодно большими или, например, дробными, данная задача может быть решена с помощью перебора.

Будем перебирать все перестановки чисел от [math]1[/math] до [math]n[/math], обозначающих номера заданий. При получении очередной перестановки просто будем пытаться выполнять задания в указанном порядке. Если значение [math]\sum \limits_{i=1}^n w_i U_i[/math], полученное при данном расположении заданий, лучше, чем предыдущие результаты, то обновляем ответ.

Данное решение будет работать за [math] \mathcal{O}(n \cdot n!)[/math].

Перебор с битовыми масками

Далее широко будет использоваться следующий факт:

Лемма:
Пусть все работы отсортированы в порядке неубывания дедлайнов [math]d_i[/math]. Тогда существует оптимальное расписание вида [math]i_1, i_2, \ldots, i_s, i_{s+1}, \ldots, i_n [/math], такое, что [math]i_1 \lt i_2 \lt \ldots \lt i_s [/math] — номера работ, которые успеют выполниться вовремя, а [math]i_{s+1}, \ldots, i_n [/math] — номера просроченных работ.
Доказательство:
[math]\triangleright[/math]

Пусть у нас есть некоторое оптимальное раписание [math]S[/math]. Получим необходимое нам расписание путем переставления некоторых работ.

  1. Если работа с номером [math] i[/math] выполнится в [math]S[/math] с опозданием, то переставим эту работу в конец. При этом, так как работа просрочна в оптимальном расписании [math]S[/math], при такой перестановке не произойдет увеличения целевой функции.
  2. Если работы с номерами [math]i[/math] и [math]j[/math] в расписании [math]S[/math] выполняются вовремя, но при этом [math]d_i \lt d_j [/math], и [math]j[/math] стоит в [math]S[/math] раньше [math]i[/math], то переставим работу с номером [math]j[/math] так, чтобы она выполнялась после работы [math]i[/math]. Таким образом, каждая из работ, находившихся в [math]S[/math] между [math]j[/math] и [math]i[/math], включая [math]i[/math], будет выполняться в новом расписании на [math]p_j[/math] единиц времени раньше. Эта перестановка не повлияет на оптимальнось расписания:
    • Ни одна из работ, котарая успевала выполниться в расписании [math]S[/math], не попадет в список просроченных работ при переставлении её на более раннее время.
    • Число работ, не успевающих выполниться вовремя, не может уменьшится, иначе бы возникло противоречие с исходным выбором [math]S[/math], как оптимального решения.
    • Поскольку [math]d_i \lt d_j [/math] и работа [math]i[/math] будет заканчиваться на [math]p_j[/math] единиц времени раньше, то стоящая сразу после нее работа [math]j[/math] тоже будет успевать выполниться.
[math]\triangleleft[/math]

Наше решение будет построено на переборе всех битовых масок. При построении решения мы будем опираться на доказанную лемму.

Если бит, соответствующий заданию с номером [math]i[/math] равен [math]1[/math], то это задание должно быть записано в список заданий, которые, возможно, успеют выполниться. Далее мы сортируем задания из этого списка по времени неубывания дедлайнов, а те задания, что не попали в этот список, должны быть отправлены в конец расписания в любом порядке. Далее проверяем полученное возможное расписание на корректность, и, в случае успеха, обновляем ответ.

Перебор всех масок может быть произведен за [math]\mathcal{O}(2 ^ n)[/math], и [math]\mathcal{O}(n)[/math] на пересчет ответа. Таким образом, это решение будет работать за [math]\mathcal{O}(n \cdot 2^n)[/math].

Псевдополиномиальное решение

В ситуации, когда времена выполнения работ [math]p_i[/math] целочисленные, а значение [math] \sum\limits_{i=1}^n p_i [/math] не очень большое, то для решения данной задачи можно применить динамическое программирование.

Описание алгоритма

Обозначим [math]T = \sum\limits_{i=1}^n p_i[/math]. Для всех [math]t = 0, 1, \ldots, T [/math] и [math]j = 1, \ldots, n[/math] будем рассчитывать [math]F_j(t)[/math] — значение целевой функции [math]\sum w_i U_i[/math], при условии, что были рассмотрены первые [math]j[/math] работ и общее время выполнения тех из них, что будут закончены вовремя, не превышает времени [math]t[/math].

  1. Если [math]0 \leqslant t \leqslant d_j [/math] и работа [math]j[/math] успевает выполниться вовремя в расписании, соответствующем [math]F_j(t)[/math], то [math]F_j(t) = F_{j- 1}(t - p_j)[/math], иначе [math]F_j(t) = F_{j- 1}(t) + w_i[/math].
  2. Если [math]t \gt d_j[/math], то [math]F_j(t) = F_{j}(d_j)[/math], поскольку все работы с номерами [math]j = 1, \ldots, j[/math], законченные позже, чем [math] d_j \geqslant \ldots \geqslant d_1 [/math], будут выполнены с опозданием.

Отсюда, получим соотношение:

[math] F_j(t) = \left \{\begin{array}{ll} \min(F_{j-1}(t-p_j), F_{j-1}(t) + w_j), & 0 \leqslant t \leqslant d_j \\ F_j(d_j), & d_j \lt t \lt T \end{array} \right. [/math]

В качестве начальных условий следует взять [math]F_j(t) = \infty [/math] при [math]t \lt 0, j = 0,\ldots, n [/math] и [math]F_0(t) = 0 [/math] при [math]t \geqslant 0 [/math].

Ответом на задачу будет [math]F_n(d_n)[/math].

Псевдокод

Приведенный ниже алгоритм вычисляет [math]F_j(t)[/math] для [math]j = 0,\ldots, n [/math] и [math]t = 0,\ldots, d_j [/math].

  • За [math]p_{max}[/math] обозначим самое большое из времен выполнения заданий.
  • Значения [math] F_j(t)[/math] будем хранить в массиве [math]F[j][t][/math].
  • В массиве [math]w[i] [/math] хранятся стоимости выполнения работ, в [math]d[i] [/math] — дедлайны, а в [math]p[i] [/math] — продолжительности выполнения.
 function [math] \mathrm{getAnswer}(p : [/math] int[math]\mathbf{[n]},[/math] [math] w : [/math] int[math]\mathbf{[n]},[/math] [math] d : [/math] int[math]\mathbf{[n]} ):[/math] int
   int [math]T = 0 [/math]
   for [math]i = 1 .. n[/math]
      [math]T = T + p[i][/math]
   int [math]F[][][/math]
   сортируем работы по неубыванию времен дедлайнов [math]d[i][/math]
   for [math]t = -p_{max}[/math] to [math]-1[/math]
     for [math]j = 0[/math] to [math]n[/math]
       [math]F[j][t] = \infty[/math]
   for [math]t = 0[/math] to [math]T[/math]
     [math]F[0][t] = 0[/math]
   for [math]j = 1[/math] to [math]n[/math]
     for [math]t = 0[/math] to [math]d[j][/math]
       if [math] F[j-1][t] + w[j]  \lt  F[j-1][t-p[j]] [/math]   
          [math] F[j][t] = F[j-1][t] + w[j] [/math]
       else
         [math]  F[j][t] = F[j-1][t-p[j]] [/math]
     for [math]t = d[j] + 1[/math] to [math]T[/math]
       [math] F[j][t] = F[j][d[j]] [/math]
   return [math] F[n][d[n]] [/math]

Для того, чтобы найти само расписание, по доказанной выше лемме, нам достаточно найти множество работ [math]L[/math], которые будут выполнены с опозданием. Это может быть сделано следующим способом:

 function [math] \mathrm{getLate}(F : [/math] int[math]\mathbf{[n][p_{max}]},[/math] [math] p : [/math] int[math]\mathbf{[n]},[/math] [math] w : [/math] int[math]\mathbf{[n]},[/math] [math] d : [/math] int[math]\mathbf{[n]} ):[/math] set<int>
   int [math]t = d[n][/math]
   set<int> [math]L = \varnothing[/math]
   for [math]j = n[/math] downto [math]1[/math]
     [math]t = \min(t, d[j])[/math]
     if [math] F[j][t] = F[j-1][t] + w[j] [/math] 
       [math] L = L \cup \{j\} [/math]
     else
       [math] t = t - p[j] [/math]
   return [math]L[/math]

Согласно лемме, само расписание будет состоять из работ, не попавших в [math]L[/math], отсортированных по неубыванию [math]d_i[/math] и работ из [math]L[/math], записанных в конец в любом порядке.

Время работы

В функции [math]\mathrm{getAnswer}[/math] пересчет динамики происходит за [math] \mathcal{O}(n T)[/math], а функция [math]\mathrm{getLate}[/math] восстанавливает список просроченных работ за [math] \mathcal{O}(n)[/math]. Дальнейшее восстановление расписания происходит в худшем случае за [math] \mathcal{O}(n \log n)[/math]. Отсюда видно, что время работы приведенного выше алгоритма — [math] \mathcal{O}\Big(n \sum\limits_{i=1}^n p_i\Big)[/math].

См. также

Источники информации

  • P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 26 - 28