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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
Строка 13: Строка 13:
 
  <tex>S = \varnothing</tex>
 
  <tex>S = \varnothing</tex>
 
  <tex>time = 0</tex>
 
  <tex>time = 0</tex>
 +
'''for''' i = 1 '''to''' n '''do'''
 +
  <tex>d_i = \min\{d_i, n\}</tex>
 
  '''for''' i = 1 '''to''' n '''do'''
 
  '''for''' i = 1 '''to''' n '''do'''
 
   '''if''' <tex>time < d_i</tex>
 
   '''if''' <tex>time < d_i</tex>
Строка 18: Строка 20:
 
   <tex>time</tex> <code>+=</code> <tex>1</tex>
 
   <tex>time</tex> <code>+=</code> <tex>1</tex>
 
    
 
    
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
+
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
 +
Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы не выполняем работы позже времени <tex>t=n</tex>).
  
 
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]].
 
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]].

Версия 14:15, 8 июня 2016

[math]1 \mid p_i=1\mid \sum U_i[/math]


Задача:
Дан один станок и [math]n[/math] работ, для которых заданы их дедлайны [math]d_i[/math], а все времена выполнения на этом станке [math]p_i = 1[/math]. Нужно успеть выполнить как можно больше работ.


Алгоритм

Чтобы получить оптимальное расписание, будем строить максимальное множество [math]S[/math] тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из [math]S[/math], упорядоченных по неубыванию дедлайнов. Будем добавлять в [math]S[/math] работы в порядке неубывания значений [math]d_j[/math], если успеваем их выполнить.

Отсортировать работы так, чтобы [math]d_1 \leqslant d_2 \leqslant \dots \leqslant d_n[/math]
[math]S = \varnothing[/math]
[math]time = 0[/math]
for i = 1 to n do
  [math]d_i = \min\{d_i, n\}[/math] 
for i = 1 to n do
  if [math]time \lt  d_i[/math]
    [math]S = S \cup \{ i \}[/math]
  [math]time[/math] += [math]1[/math]
  

Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за [math]O(n)[/math], а значит и весь алгоритм будет работать за [math]O(n)[/math]. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле [math]d_i = \min\{d_i, n\}[/math] (в оптимальном расписании мы не выполняем работы позже времени [math]t=n[/math]).

В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [math]1 \mid \mid \sum w_{i}U_{i}[/math].

См. также

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

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 86 стр. — ISBN 978-3-540-69515-8