|
|
| Строка 5: |
Строка 5: |
| | }} | | }} |
| | ==Алгоритм== | | ==Алгоритм== |
| − | Идея алгоритма состоит в том, что на шаге <tex>k</tex> строим оптимальное решение для первых <tex>k</tex> работ с наименьшими дедлайнами.
| |
| | | | |
| − | Пусть работы отсортированы в порядке возрастания дедлайнов. Пусть мы уже рассмотрели первые <tex>k</tex> работ, тогда множество <tex>S_k</tex> содержит только те работы, которые мы успеваем выполнить в порядке не убывания дедлайнов при оптимальном расписании. Рассмотрим работу <tex>k+1</tex>. Если мы ее успеваем выполнить данную работу, до наступления дедлайна, то добавим в множество <tex>S_{k}</tex> и получим множество <tex>S_{k+1}</tex>. Если же <tex>k+1</tex> работу мы не успеваем выполнить до дедлайна, то найдем в <tex>S_k</tex> работу <tex>l</tex> c наименьшим весом <tex>w_{l}</tex> и заменим ее на работу <tex>k+1</tex>.
| |
| | | | |
| − | Таким образом, рассмотрев все работы, мы получим <tex>S_{n}</tex> — множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.
| |
| − |
| |
| − | ==Псевдокод==
| |
| − | Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex>m \leqslant d_{1} \leqslant d_{2} \leqslant \ldots \leqslant d_{n}</tex>. Все работы, дедлайн которых меньше <tex>m</tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
| |
| − |
| |
| − | <tex>S</tex> {{---}} множество непросроченных работ, <tex>Check</tex> {{---}} функция, решающая задачу [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]].
| |
| − |
| |
| − | S = <tex>\varnothing</tex>
| |
| − | '''for''' i = 1 to n
| |
| − | S = <tex> S \cup \{i\} </tex>
| |
| − | '''if''' '''not''' Check(s) :
| |
| − | найти такое <tex>k</tex>, что <tex>w_{k} = \min \{ w_{j} \mid j \in S\}</tex>
| |
| − | S = <tex>S \setminus \{k\}</tex>
| |
| | | | |
| | ==Доказательство корректности== | | ==Доказательство корректности== |
| | | | |
| − | {{Утверждение
| |
| − | |statement=Алгоритм строит корректное расписание.
| |
| − | |proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
| |
| − | }}
| |
| − |
| |
| − | {{Теорема
| |
| − | |statement=Построенное данным алгоритмом расписание оптимально.
| |
| − | |proof=
| |
| − | Пусть <tex> S^* </tex> множество непросроченных работ в оптимальном расписании. Также пусть <tex> l </tex> {{---}} первая работа из множества <tex> S </tex>, которая не входит в <tex> S^* </tex>, а <tex> k </tex> {{---}} первая работа из <tex> S^* </tex>, не содержащаяся в <tex> S </tex>. Мы можем предполагать существование этих работ, потому что <tex> S^* </tex> не может содержать <tex> S </tex> как подмножество, иначе это противоречило бы построению <tex> S </tex>. С другой стороны, если <tex> S^* \subseteq S </tex>, то <tex> S </tex> должно быть тоже оптимальным, и правильность алгоритма доказана.
| |
| − |
| |
| − | Для доказательства покажем, что мы можем заменить работу <tex> k </tex> на работу <tex> l </tex> в оптимальном расписании, не увеличивая минимизируемую функцию.
| |
| − |
| |
| − | Рассмотрим два случая:
| |
| − |
| |
| − | *<tex> l < k </tex>
| |
| − | Так как работа <tex> k </tex> не содержится в <tex> S </tex>, то либо она не была добавлена при ее рассмотрении, либо была заменена работой, рассмотренной позднее. В любом случае это означает, что <tex> w_{k} \leqslant w_{l} </tex>. Так же по определению <tex> k </tex> все работы <tex> i \in S^* : i < k </tex> должны содержаться и в <tex> S </tex>. Но тогда заменив в оптимальном расписании <tex> k </tex> на <tex> l </tex>, мы сохраним корректность расписания и не увеличим минимизируемую функцию.
| |
| − | *<tex> k < l </tex>
| |
| − | Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, <tex> d_{k} \leqslant d_{l} </tex>, и замена работы <tex> k </tex> на <tex> l </tex> в оптимальном расписании <tex> S^* </tex> не может сделать его некорректным. Тогда для доказательства нам осталось показать, что <tex> w_{k} \leqslant w_{l} </tex>.
| |
| − |
| |
| − | Пусть <tex> k_{i_{0}} = k </tex> {{---}} работа, замененная работой <tex> i_{0} </tex> в процессе построения <tex> S </tex>, и пусть <tex> k_{i_{1}}, \ldots, k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>. <tex> i_{0} < i_{1} < \ldots < i_{r} </tex>. Будем говорить, что "работа <tex> i_{v} </tex> подавляет <tex> i_{m} </tex>", где <tex> m < v </tex>, если <tex> k_{i_{v}} \leqslant i_{m} </tex>. В таком случае получаем, что <tex> w_{k_{i_{v}}} \geqslant w_{k_{i_{m}}}</tex>, потому что в противном случае работа <tex> k_{i_{v}} </tex> была бы исключена из <tex> S </tex> раньше чем <tex> k_{i_{m}} </tex>.
| |
| − |
| |
| − | Если в последовательности <tex> i_{0} < i_{1} < \ldots < i_{r} </tex> существует подпоследовательность <tex> j_{0} = i_{0} < j_{1} < \ldots < j_{s} </tex> такая, что <tex> j_{v + 1} </tex> подавляет <tex> j_{v} </tex> для всех <tex> v = 0,1, \ldots, s - 1 </tex> и <tex> j_{s - 1} < l \leqslant j_{s} </tex>, то получаем, что <tex> w_{l} \geqslant w_{k_{j_{s}}} \geqslant \ldots \geqslant w_{k_{j_{0}}} = w_{k} </tex>, что доказывает оптимальность расписания <tex> S </tex>.
| |
| − |
| |
| − | Покажем, что отсутствие такой подпоследовательности приведет нас к противоречию, из чего будет следовать ее существование.
| |
| − |
| |
| − | Предположим, что такой подпоследовательности не существует. Тогда найдем наименьшее <tex> t </tex> такое, что не существует работы <tex> i_{v} : v > t </tex>, которая бы подавляла работу <tex> i_{t} </tex>, и <tex> i_{t} </tex> было бы меньше <tex> l </tex>. По определению <tex> l </tex> и <tex> i_{t} </tex> и из факта, что <tex> i_{t} < l </tex>, получаем, что после добавления во множество <tex> S </tex> работы <tex> i_{t} </tex>, ни одна из работ, рассмотренных ранее, не будет удалена из <tex> S </tex>, а так же все эти работы содержатся и в оптимальном расписании <tex> S^* </tex>, поскольку <tex> i_t < l </tex>.
| |
| − |
| |
| − | Пусть <tex> S_t </tex> это множество <tex> S </tex> после замены работы <tex> k_{i_t} </tex> на <tex> i_t </tex>. Если <tex> k_{i_t} > k </tex>, то в оптимальном расписании <tex> S^* </tex> мы можем заменить работу <tex> k </tex> на <tex> k_{i_t} </tex>, поскольку <tex> d_{k_{i_t}} \geqslant d_k </tex>. Но так как <tex> S_t \subset S^* </tex>, то все работы из множества <tex> S_t \cup \{k_{i_t}\} </tex> могут быть выполнены до их дедлайнов, что противоречит построению <tex> S </tex>. Следовательно, <tex> k_{i_t} < k </tex>. Тогда аналогично предыдущему случаю получаем, что все работы из множества <tex> S_t \cup \{k\} </tex> могут быть выполнены вовремя. Кроме того, все работы из <tex> \{ j \in S_t \mid j < k \} \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что следует из построения <tex> S_t </tex>. Но тогда получается, что все работы и из множества <tex> S_t \cup \{k_{i_t}\} </tex> так же могут быть выполнены вовремя, что опять приводит нас к противоречию с построением <tex> S </tex>.
| |
| − | }}
| |
| | | | |
| | ==Время работы== | | ==Время работы== |
| − | Время работы зависит от того, на сколько быстро мы будем добавлять, находить и удалять работы из множества <tex>S</tex>. В качестве <tex>S</tex> можно использовать [[Двоичная куча | двоичную кучу]] или [[Красно-черное дерево | красно-черное дерево]] и тогда все нужные нам операции будут выполняться за <tex>O(\log n)</tex>. Тогда время алгоритма будет <tex>O(n \cdot (\log n + T(Check)))</tex>. Так как <tex>T(Check)=O(n \cdot m)</tex>, то время алгоритма <tex>O(n^2 \cdot m)</tex>
| |
| | | | |
| | ==См. также== | | ==См. также== |
| Строка 63: |
Строка 18: |
| | | | |
| | ==Источники информации== | | ==Источники информации== |
| − | * Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 168. стр. | + | * Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} c. 168 - 171. ISBN 978-3-540-69515-8 |
| | | | |
| | [[Категория: Алгоритмы и структуры данных]] | | [[Категория: Алгоритмы и структуры данных]] |
| | [[Категория: Теория расписаний]] | | [[Категория: Теория расписаний]] |
