1sumu

Задача:

Дан один станок и [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