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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (переименовал P1sumu в 1sumu: название в нестандартном формате)
м (rollbackEdits.php mass rollback)
 
(не показано 9 промежуточных версий 2 участников)
Строка 1: Строка 1:
==Постановка задачи==
+
{{Шаблон:Задача
 +
|definition =  
 
Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполнения на этом станке <tex>p_i</tex> и дедлайны <tex>d_i</tex>. Нужно успеть выполнить как можно больше работ.
 
Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполнения на этом станке <tex>p_i</tex> и дедлайны <tex>d_i</tex>. Нужно успеть выполнить как можно больше работ.
 +
}}
 
==Алгоритм==
 
==Алгоритм==
 
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
 
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
 
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.
 
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.
  
    <span style="color:Green">// Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex></span>
+
Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>
    <tex>S \leftarrow \varnothing</tex>;
+
<tex>S = \varnothing</tex>
    <tex>time \leftarrow 0</tex>;
+
<tex>time = 0</tex>
    '''for''' i := 1 '''to''' n '''do'''
+
'''for''' i = 1 '''to''' n '''do'''
        <tex>S \leftarrow S \cup \{ i \}</tex>;
+
    <tex>S = S \cup \{ i \}</tex>
        <tex>time</tex> <code>+=</code> <tex>p_i</tex>;
+
    <tex>time</tex> <code>+=</code> <tex>p_i</tex>
        '''if''' <tex>t > d_i</tex>
+
    '''if''' <tex>t > d_i</tex>
            находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>;
+
        находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>
            <tex>S = S \setminus\{j\}</tex>;
+
        <tex>S = S \setminus\{j\}</tex>
            <tex>time</tex> <code>-=</code> <tex>p_j</tex>;
+
        <tex>time</tex> <code>-=</code> <tex>p_j</tex>
 
Алгоритм будет работать за <tex>O(n \log n)</tex>.
 
Алгоритм будет работать за <tex>O(n \log n)</tex>.
  
 +
==Оптимальность и корректность==
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Этот алгоритм строит оптимальное расписание.
+
Приведенный выше алгоритм строит оптимальное расписание.
 
|proof=
 
|proof=
Разделим множество работ <tex>P</tex> на множество тех, которые успеют выполниться - <tex>S</tex> и которые не успеют - <tex>F</tex>.
+
Разделим множество работ <tex>P</tex> на два: <tex>S</tex> — множество работ, которые успеют выполниться и <tex>F</tex> — работы, которые не успеют выполниться.
Пусть <tex>j</tex> - первая работа, которая была удалена из <tex>S</tex>. Докажем, что существует оптимальное расписание <tex>P = (S, T)</tex>, в котором <tex>j \in F</tex>. Обозначим через <tex>k</tex> ту работу, которая была последней добавлена в <tex>S</tex>. Тогда <tex>p_j = \max\limits_{i = 1 \dots k} p_i</tex>. При этом в последовательности работ <tex>1, 2, \dots, j-1 j+1, dots, k</tex> не будет ни одной невыполненной работы, поскольку в последовательности <tex>1, 2, \dots, k-1</tex> все работы выполняются вовремя и <tex>p_k \leqslant p_j</tex>. Заменим <tex>j</tex> на <tex>k</tex> и отсортируем все работы.  
+
Пусть <tex>j</tex> первая работа, которая была удалена из <tex>S</tex>. Докажем, что существует оптимальное расписание <tex>P = (S, T)</tex>, в котором <tex>j \in F</tex>. Обозначим через <tex>k</tex> ту работу, которая была последней добавлена в <tex>S</tex>. Тогда <tex>p_j = \max\limits_{i = 1 \dots k} p_i</tex>. При этом в последовательности работ <tex>1, 2, \dots, j-1, j+1, \dots, k</tex> не будет ни одной невыполненной работы, поскольку в последовательности <tex>1, 2, \dots, k-1</tex> все работы выполняются вовремя и <tex>p_k \leqslant p_j</tex>. Заменим <tex>j</tex> на <tex>k</tex> и отсортируем все работы.  
 
Теперь рассмотрим оптимальное расписание <tex>P' = (S', F')</tex>, где <tex>j \in S'</tex>. В нём существует последовательность <tex>\pi</tex>: <tex>\pi(1), \dots, \pi(m), \dots, \pi(r), \pi(r+1), \dots, \pi(n)</tex>, такая, что
 
Теперь рассмотрим оптимальное расписание <tex>P' = (S', F')</tex>, где <tex>j \in S'</tex>. В нём существует последовательность <tex>\pi</tex>: <tex>\pi(1), \dots, \pi(m), \dots, \pi(r), \pi(r+1), \dots, \pi(n)</tex>, такая, что
  
Строка 40: Строка 43:
  
 
Таким образом, мы получили оптимальное расписание <tex>P = (S, F)</tex>, в котором <tex>j \in F</tex>.
 
Таким образом, мы получили оптимальное расписание <tex>P = (S, F)</tex>, в котором <tex>j \in F</tex>.
Теперь докажем теорему индукцией по числу работ. Очевидно, при <tex>n = 1</tex> она выполняется. Предположим, что алгоритм верен для <tex>n - 1</tex> работы. Пусть <tex>P = (S, T)</tex> - расписание, построенное алгоритмом, а <tex>P' = (S', T')</tex> - оптимальное расписание с <tex>j \in F'</tex>. Тогда, по отимальности, <tex>|S| \leqslant |S'|</tex>.
+
Теперь докажем теорему индукцией по числу работ. Очевидно, при <tex>n = 1</tex> она выполняется. Предположим, что алгоритм верен для <tex>n - 1</tex> работы. Пусть <tex>P = (S, T)</tex> расписание, построенное алгоритмом, а <tex>P' = (S', T')</tex> оптимальное расписание с <tex>j \in F'</tex>. Тогда, по отимальности, <tex>|S| \leqslant |S'|</tex>.
 
Если применить алгоритм ко множеству <tex>\{1, \dots, j-1, j+1, \dots, n\}</tex>, то получим оптимальное расписание для <tex>(S, F\setminus \{j\})</tex>. Т.к. для задачи с меньшим числом станков им будет являться <tex>(S', F' \setminus \{j\})</tex>, то <tex>|S'| \leqslant |S|</tex>, и, следовательно, <tex>|S| = |S'|</tex> и <tex>P</tex> является оптимальным расписанием.
 
Если применить алгоритм ко множеству <tex>\{1, \dots, j-1, j+1, \dots, n\}</tex>, то получим оптимальное расписание для <tex>(S, F\setminus \{j\})</tex>. Т.к. для задачи с меньшим числом станков им будет являться <tex>(S', F' \setminus \{j\})</tex>, то <tex>|S'| \leqslant |S|</tex>, и, следовательно, <tex>|S| = |S'|</tex> и <tex>P</tex> является оптимальным расписанием.
 
}}
 
}}
Строка 46: Строка 49:
 
==Источники информации==
 
==Источники информации==
 
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
 
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8
 +
 +
== См. также ==
 +
* [[Классификация задач]]
 +
* [[1ripi1sumwc|<tex>1 \mid r_{i}, p_i=1\mid \sum w_{i}C_{i}</tex>]]
 +
* [[1pi1sumwu|<tex>1 \mid p_{i} = 1 \mid \sum w_{i}U_{i}</tex>]]
 +
* [[1ripi1sumf|<tex>1 \mid r_i, p_i = 1 \mid \sum f_i</tex>]]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

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

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

Алгоритм

Чтобы получить оптимальное расписание, будем строить максимальное множество [math]S[/math] тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из [math]S[/math], упорядоченных по неубыванию дедлайнов. Будем добавлять в [math]S[/math] работы в порядке неубывания значений [math]d_j[/math]. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из [math]S[/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]S = S \cup \{ i \}[/math]
    [math]time[/math] += [math]p_i[/math]
    if [math]t \gt  d_i[/math]
        находим в [math]S[/math] работу [math]j[/math] с наибольшим [math]p_j[/math]
        [math]S = S \setminus\{j\}[/math]
        [math]time[/math] -= [math]p_j[/math]

Алгоритм будет работать за [math]O(n \log n)[/math].

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

Теорема:
Приведенный выше алгоритм строит оптимальное расписание.
Доказательство:
[math]\triangleright[/math]

Разделим множество работ [math]P[/math] на два: [math]S[/math] — множество работ, которые успеют выполниться и [math]F[/math] — работы, которые не успеют выполниться. Пусть [math]j[/math] — первая работа, которая была удалена из [math]S[/math]. Докажем, что существует оптимальное расписание [math]P = (S, T)[/math], в котором [math]j \in F[/math]. Обозначим через [math]k[/math] ту работу, которая была последней добавлена в [math]S[/math]. Тогда [math]p_j = \max\limits_{i = 1 \dots k} p_i[/math]. При этом в последовательности работ [math]1, 2, \dots, j-1, j+1, \dots, k[/math] не будет ни одной невыполненной работы, поскольку в последовательности [math]1, 2, \dots, k-1[/math] все работы выполняются вовремя и [math]p_k \leqslant p_j[/math]. Заменим [math]j[/math] на [math]k[/math] и отсортируем все работы. Теперь рассмотрим оптимальное расписание [math]P' = (S', F')[/math], где [math]j \in S'[/math]. В нём существует последовательность [math]\pi[/math]: [math]\pi(1), \dots, \pi(m), \dots, \pi(r), \pi(r+1), \dots, \pi(n)[/math], такая, что

  • [math]F' = \{\pi(r+1), \dots, \pi(n)\}[/math];
  • [math]d_{\pi(1)} \leqslant \dots \leqslant d_{\pi(r)}[/math];
  • [math]\{\pi(1), \dots, \pi(m)\} \subseteq \{1, \dots, k\}[/math];
  • [math]\{\pi(m+1), \dots, \pi(r)\} \subseteq \{k+1, \dots, n\}[/math];
  • [math]j \in \{\pi(1), \dots, \pi(m)\}[/math];

Такое [math]m[/math] всегда найдётся, т.к. [math]d_1 \leqslant d_2 \leqslant \dots \leqslant d_n[/math], а последнее будет следовать из того, что [math]j \in S' \cap \{1, \dots, k\}[/math]. Из того, что [math]\{\pi(1), \dots, \pi(m)\} \subseteq S'[/math] следует, что выполнятся все работы из [math]\{\pi(1), \dots, \pi(m)\}[/math]. С другой стороны, при любом расписании не будет выполнена какая-то работа из [math]\{1, \dots, k\}[/math]. Поэтому [math]\{\pi(1), \dots, \pi(m)\} \subset \{1, \dots, k\}[/math], при этом существует работа [math]h \notin \{\pi(1), \dots, \pi(m)\}[/math]. Удалим работу [math]j[/math] из [math]\{\pi(1), \dots, \pi(m)\}[/math] и заменим на [math]h[/math]. Если отсортируем получившееся множество, то все работы в нём выполнятся, т.к. [math]\{\pi(1), \dots, \pi(m)\} \cup \{h\} \cap \{j\} \subseteq \{1, \dots, k\} \setminus \{j\}[/math], а оно обладает таким свойством. Если добавим работы [math]\pi(m+1), \dots, \pi(r)[/math] к множеству [math]\{\pi(1), \dots, \pi(m)\} \cup \{h\} \cap \{j\}[/math] и отсортируем его по неубыванию дедлайнов, то все работы в нём выполнятся, т.к. из [math]p_h \leqslant p_j[/math] следует, что

[math]\sum_{i=1}^{m} p_{\pi(i)} - p_j + p_h \leqslant \sum_{i=1}^{m} p_{\pi(i)}[/math].

Таким образом, мы получили оптимальное расписание [math]P = (S, F)[/math], в котором [math]j \in F[/math]. Теперь докажем теорему индукцией по числу работ. Очевидно, при [math]n = 1[/math] она выполняется. Предположим, что алгоритм верен для [math]n - 1[/math] работы. Пусть [math]P = (S, T)[/math] — расписание, построенное алгоритмом, а [math]P' = (S', T')[/math] — оптимальное расписание с [math]j \in F'[/math]. Тогда, по отимальности, [math]|S| \leqslant |S'|[/math].

Если применить алгоритм ко множеству [math]\{1, \dots, j-1, j+1, \dots, n\}[/math], то получим оптимальное расписание для [math](S, F\setminus \{j\})[/math]. Т.к. для задачи с меньшим числом станков им будет являться [math](S', F' \setminus \{j\})[/math], то [math]|S'| \leqslant |S|[/math], и, следовательно, [math]|S| = |S'|[/math] и [math]P[/math] является оптимальным расписанием.
[math]\triangleleft[/math]

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

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

См. также