Изменения
Нет описания правки
Дан один станок и <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>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>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
== См. также ==
* [[Классификация задач]]
* [[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>]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
