Викиконспекты - Вклад участника [ru]

1sumu

2016-05-13T12:51:22Z

217.66.158.63: /* Источники информации */

==Постановка задачи==
Дан один станок и <tex>n</tex> работ, для которых заданы их времена выполнения на этом станке <tex>p_i</tex> и дедлайны <tex>d_i</tex>. Нужно успеть выполнить как можно больше работ.
==Алгоритм==
Чтобы получить оптимальное расписание, будем строить максимальное множество <tex>S</tex> тех работ, которые успеют выполниться. Само расписание тогда будет состоять из всех работ из <tex>S</tex>, упорядоченных по неубыванию дедлайнов.
Будем добавлять в <tex>S</tex> работы в порядке неубывания значений <tex>d_j</tex>. Если вновь добавленная работа не успевает выполниться до дедлайна, то найдём и удалим из <tex>S</tex> работу с самым большим временем выполнения.

Отсортировать работы так, чтобы <tex>d_1 \leqslant d_2 \leqslant \dots \leqslant d_n</tex>;
<tex>S \leftarrow \varnothing</tex>;
<tex>time \leftarrow 0</tex>;
<tex>FOR</tex> <tex>i := 1\dots n</tex> <tex>DO</tex>
<tex>S \leftarrow S \cup \{ i \}</tex>;
<tex>t</tex> <code>+=</code> <tex>p_i</tex>;
<tex>IF</tex> <tex>t > d_i</tex>
находим в <tex>S</tex> работу <tex>j</tex> с наибольшим <tex>p_j</tex>;
<tex>S = S \setminus\{j\}</tex>;
<tex>t</tex> <code>-=</code> <tex>p_j</tex>;
Алгоритм будет работать за <tex>O(n \log n)</tex>.

{{Теорема
|statement=
Этот алгоритм строит оптимальное расписание.
|proof=
Разделим множество работ <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>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>F' = \{\pi(r+1), \dots, \pi(n)\}</tex>;

* <tex>d_{\pi(1)} \leqslant \dots \leqslant d_{\pi(r)}</tex>;

* <tex>\{\pi(1), \dots, \pi(m)\} \subseteq \{1, \dots, k\}</tex>;

* <tex>\{\pi(m+1), \dots, \pi(r)\} \subseteq \{k+1, \dots, n\}</tex>;

* <tex>j \in \{\pi(1), \dots, \pi(m)\}</tex>;

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

<tex>\sum_{i=1}^{m} p_{\pi(i)} - p_j + p_h \leqslant \sum_{i=1}^{m} p_{\pi(i)}</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>\{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> является оптимальным расписанием.
}}

==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 86 стр. {{---}} ISBN 978-3-540-69515-8

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]

1sumu

2016-05-13T12:49:54Z

217.66.158.63: /* Литература */