Изменения
Новая страница: «<tex dpi = "200"> 1 \mid p_{i}=1 \mid \sum\nolimits w_iU_i</tex> {{Задача |definition = Дано <tex> n </tex> работ и <tex> 1 </tex> станок. ...»
<tex dpi = "200"> 1 \mid p_{i}=1 \mid \sum\nolimits w_iU_i</tex>
{{Задача
|definition = Дано <tex> n </tex> работ и <tex> 1 </tex> станок. Для каждой работы известны её дедлайн <tex> d_{i} </tex> и вес <tex> w_{i} </tex>. Время выполнения всех работ <tex> p_i </tex> равно <tex> 1 </tex>. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.
}}
== Алгоритм ==
Идея алгоритма состоит в том, чтобы на шаге <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> с наименьшим весом <tex> w_{l} </tex> и заменим ее на работу <tex> k + 1 </tex>.
Таким образом, рассмотрев все работы, мы получим <tex> S_{n} </tex> {{---}} множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.
== Псевдокод ==
Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex> 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n} </tex>. Все работы, дедлайн которых равен <tex> 0 </tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
<tex> s </tex> {{---}} множество непросроченных работ, <tex> t </tex> {{---}} текущее время.
'''Set''' p1sumwu('''int''' <tex>w[i]</tex>, '''int''' <tex>d[i]</tex>):
'''int''' <tex> t = 1</tex>
'''set''' <tex>s</tex>
'''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>
<tex> s = s \cup \{i\} </tex>
'''if''' <tex> d_{i} \geqslant t </tex>
<tex> t = t + 1 </tex>
'''else'''
найти такое <tex> k </tex>, что <tex> w_{k} = \min \{ w_{j} \mid j \in s\} </tex>
<tex> s = s \setminus \{k\} </tex>
'''return''' <tex>s</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}}, ..., k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>. <tex> i_{0} < i_{1} < ... < 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} < ... < i_{r} </tex> существует подпоследовательность <tex> j_{0} = i_{0} < j_{1} < ... < j_{s} </tex> такая, что <tex> j_{v + 1} </tex> подавляет <tex> j_{v} </tex> для всех <tex> v = 0,1, ..., s - 1 </tex> и <tex> j_{s - 1} < l \leqslant j_{s} </tex>, то получаем, что <tex> w_{l} \geqslant w_{k_{j_{s}}} \geqslant ... \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 | 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\log n) </tex>. Например, такими структурами данных являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
в
== Более простой случай ==
Задачу <tex> 1 \mid p_{i}=1 \mid \sum\nolimits U_i</tex> можно решить за <tex>O(n)</tex>. Рассмотрим следующий алгоритм. Работы, значение <tex>d</tex> у которых больше либо равно <tex>n</tex>, поместим в конец расписания. Для остальных работ заведём <tex>n-1</tex> множество <tex>S_{1}, S_{2} \dots S_{n-1}</tex>. В множестве <tex>S_{i}</tex> будем хранить номера работ, у которых <tex>d = i</tex>. Далее для каждого множества будем по очереди добавлять работы, которые успеваем сделать, в расписание (как в строчках 3-6 предыдущего алгоритма). Те работы, которые не успеваем сделать, добавим в конец расписания. Всего будет выполнено O(n) операций и время работы алгоритма, таким образом, составляет <tex>O(n)</tex>.
== Источники информации ==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 96 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
{{Задача
|definition = Дано <tex> n </tex> работ и <tex> 1 </tex> станок. Для каждой работы известны её дедлайн <tex> d_{i} </tex> и вес <tex> w_{i} </tex>. Время выполнения всех работ <tex> p_i </tex> равно <tex> 1 </tex>. Требуется минимизировать <tex>\sum w_{i} U_{i}</tex>, то есть суммарный вес всех просроченных работ.
}}
== Алгоритм ==
Идея алгоритма состоит в том, чтобы на шаге <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> с наименьшим весом <tex> w_{l} </tex> и заменим ее на работу <tex> k + 1 </tex>.
Таким образом, рассмотрев все работы, мы получим <tex> S_{n} </tex> {{---}} множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.
== Псевдокод ==
Предполагаем, что перед началом выполнения алгоритма выполняется, что <tex> 1 \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n} </tex>. Все работы, дедлайн которых равен <tex> 0 </tex>, мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.
<tex> s </tex> {{---}} множество непросроченных работ, <tex> t </tex> {{---}} текущее время.
'''Set''' p1sumwu('''int''' <tex>w[i]</tex>, '''int''' <tex>d[i]</tex>):
'''int''' <tex> t = 1</tex>
'''set''' <tex>s</tex>
'''for''' <tex> i = 1 </tex> '''to''' <tex> n </tex>
<tex> s = s \cup \{i\} </tex>
'''if''' <tex> d_{i} \geqslant t </tex>
<tex> t = t + 1 </tex>
'''else'''
найти такое <tex> k </tex>, что <tex> w_{k} = \min \{ w_{j} \mid j \in s\} </tex>
<tex> s = s \setminus \{k\} </tex>
'''return''' <tex>s</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}}, ..., k_{i_{r}} </tex> {{---}} последовательность работ, которые были исключены из <tex> S </tex> после замены <tex> k </tex>, причем работа <tex> k_{i_{v}} </tex> была заменена работой <tex> i_{v} </tex>. <tex> i_{0} < i_{1} < ... < 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} < ... < i_{r} </tex> существует подпоследовательность <tex> j_{0} = i_{0} < j_{1} < ... < j_{s} </tex> такая, что <tex> j_{v + 1} </tex> подавляет <tex> j_{v} </tex> для всех <tex> v = 0,1, ..., s - 1 </tex> и <tex> j_{s - 1} < l \leqslant j_{s} </tex>, то получаем, что <tex> w_{l} \geqslant w_{k_{j_{s}}} \geqslant ... \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 | 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\log n) </tex>. Например, такими структурами данных являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
в
== Более простой случай ==
Задачу <tex> 1 \mid p_{i}=1 \mid \sum\nolimits U_i</tex> можно решить за <tex>O(n)</tex>. Рассмотрим следующий алгоритм. Работы, значение <tex>d</tex> у которых больше либо равно <tex>n</tex>, поместим в конец расписания. Для остальных работ заведём <tex>n-1</tex> множество <tex>S_{1}, S_{2} \dots S_{n-1}</tex>. В множестве <tex>S_{i}</tex> будем хранить номера работ, у которых <tex>d = i</tex>. Далее для каждого множества будем по очереди добавлять работы, которые успеваем сделать, в расписание (как в строчках 3-6 предыдущего алгоритма). Те работы, которые не успеваем сделать, добавим в конец расписания. Всего будет выполнено O(n) операций и время работы алгоритма, таким образом, составляет <tex>O(n)</tex>.
== Источники информации ==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 96 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
