1sumu

Материал из Викиконспекты
Перейти к: навигация, поиск
Задача:
Дан один станок и n работ, для которых заданы их времена выполнения на этом станке p_i и дедлайны d_i. Нужно успеть выполнить как можно больше работ.

Содержание

[править] Алгоритм

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

Отсортировать работы так, чтобы d_1 \leqslant d_2 \leqslant \dots \leqslant d_n
S = \varnothing
time = 0
for i = 1 to n do
    S = S \cup \{ i \}
    time += p_i
    if t > d_i
        находим в S работу j с наибольшим p_j
        S = S \setminus\{j\}
        time -= p_j

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

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

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

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

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

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

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

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

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

[править] Источники информации

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

[править] См. также

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты