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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Шаблон:Задача |definition = Дан один станок и <tex>n</tex> работ, для которых заданы их дедлайны <tex>...»)
 
м (Псевдокод)
 
(не показано 10 промежуточных версий 3 участников)
Строка 1: Строка 1:
 +
<tex dpi = "200" >1 \mid p_i=1\mid \sum U_i</tex>
 +
 
{{Шаблон:Задача
 
{{Шаблон:Задача
 
|definition =  
 
|definition =  
Строка 5: Строка 7:
  
 
==Алгоритм==
 
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
 
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>, если успеваем их выполнить.
 
  
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
+
===Описание алгоритма===
<tex>S = \varnothing</tex>
+
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов. Во время сортировки стоит учитывать, что дедлайны могут значительно превосходить количество задач. В таком случае необходимо предварительно пересчитать дедлайны по формуле <tex>d_i = \min\{d_i, n\}</tex> (в оптимальном расписании мы выполняем все работы до времени <tex>time=n</tex>). Для упорядочивания дедлайнов будем использовать  [[Карманная сортировка|карманную сортировку]].
<tex>time = 0</tex>
 
'''for''' i = 1 '''to''' n '''do'''
 
  '''if''' <tex>time < d_i</tex>
 
    <tex>S = S \cup \{ i \}</tex>
 
  <tex>time</tex> <code>+=</code> <tex>1</tex>
 
 
 
Cортировку работ по неубыванию дедлайнов осуществляем с помощью сортировки подсчетом за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
 
  
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]].
+
===Псевдокод===
 +
'''function''' schedule(d: '''int[n]'''): '''list<int>'''
 +
  '''list<int>''' S = <tex>\varnothing</tex>
 +
  '''int''' time = 0
 +
  '''for''' i = 1 '''to''' n '''do'''
 +
    d[i] = min(d[i], n)
 +
  Сортиуем d
 +
  '''for''' i = 1 '''to''' n '''do'''
 +
    '''if''' time < d[i]
 +
      S = S <tex>\cup</tex> {i}
 +
      time += 1
 +
  '''return''' S
  
==Источники информации==
+
Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение <tex> time = 0</tex>. После рассмотрения очередной работы мы будем добавлять ее в расписание и  увеличивать <tex> time</tex> на <tex>1</tex>. Тогда, если значение <tex> time</tex> становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с <tex>d_i = 0</tex> заранее отметим как просроченные.
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
+
 
 +
===Время работы===
 +
Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за <tex>O(n)</tex>, а значит и весь алгоритм будет работать за <tex>O(n)</tex>.
 +
 
 +
===Корректность и оптимальность===
 +
В результате выполнения данного алгоритма будет получено корректное расписание, в котором каждая работа встречается не более одного раза. Вначале расписания будут стоять все работы, которые мы успеваем выполнить до дедлайна. Остальные работы дописываются в конец в произвольном порядке.
 +
 
 +
Оптимальность полученного расписания доказывается аналогично [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]].
  
 
== См. также ==
 
== См. также ==
Строка 28: Строка 39:
 
* [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]]
 
* [[1sumwu|<tex>1 \mid  \mid \sum w_{i}U_{i}</tex>]]
  
[[Категория: Дискретная математика и алгоритмы]]
+
==Источники информации==
 +
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
 +
 
 +
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 22:42, 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]d_i = \min\{d_i, n\}[/math] (в оптимальном расписании мы выполняем все работы до времени [math]time=n[/math]). Для упорядочивания дедлайнов будем использовать карманную сортировку.

Псевдокод[править]

function schedule(d: int[n]): list<int>
  list<int> S = [math]\varnothing[/math]
  int time = 0
  for i = 1 to n do
    d[i] = min(d[i], n)
  Сортиуем d
  for i = 1 to n do
    if time < d[i]
      S = S [math]\cup[/math] {i}
      time += 1
  return S

Во избежание лишнего копирования массивов, мы можем делать проход по массиву блоков (bucket'ов) и для каждого блока проходить по спискам работ внутри него. Начальное значение [math] time = 0[/math]. После рассмотрения очередной работы мы будем добавлять ее в расписание и увеличивать [math] time[/math] на [math]1[/math]. Тогда, если значение [math] time[/math] становится равным номеру блока, то мы переходим к следующему блоку, а нерассмотренные задачи помечаем как просроченные и выполняем в конце. Работы с [math]d_i = 0[/math] заранее отметим как просроченные.

Время работы[править]

Cортировку работ по неубыванию дедлайнов осуществляем с помощью карманной сортировки за [math]O(n)[/math], а значит и весь алгоритм будет работать за [math]O(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