Opij1sumwu — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(См. также)
(Доказательство корректности)
Строка 28: Строка 28:
 
|statement=Алгоритм строит корректное расписание.
 
|statement=Алгоритм строит корректное расписание.
 
|proof=Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
 
|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>.
 
}}
 
}}
  

Версия 14:19, 14 мая 2016

[math] O \mid p_{i,j} = 1 \mid \sum w_{i} U_{i} [/math]

Задача:
Дано [math]m[/math] одинаковых станков, которые работают параллельно, и [math]n[/math] работ, которые необходимо выполнить в произвольном порядке на всех станках. Любая работа на любом станке выполняется за единицу времени. Для каждой работы есть время окончания [math]d_i[/math] — время, до которого она должна быть выполнена. Требуется минимизировать [math]\sum w_{i} U_{i}[/math], то есть суммарный вес всех просроченных работ.

Алгоритм

Идея алгоритма состоит в том, что на шаге [math]k[/math] строим оптимальное решение для первых [math]k[/math] работ с наименьшими дедлайнами.

Пусть работы отсортированы в порядке возрастания дедлайнов. Пусть мы уже рассмотрели первые [math]k[/math] работ, тогда множество [math]S_k[/math] содержит только те работы, которые мы успеваем выполнить в порядке возрастания дедлайнов при оптимальном расписании. Рассмотрим работу [math]k+1[/math]. Если мы ее успеваем выполнить данную работу, до наступления дедлайна, то добавим в множество [math]S_{k}[/math] и получим множество [math]S_{k+1}[/math]. Если же [math]k+1[/math] работу мы не успеваем выполнить до дедлайна, то найдем в [math]S_k[/math] работу [math]l[/math] c наименьшим весом [math]w_{l}[/math] и заменим ее на работу [math]k+1[/math].

Таким образом, рассмотрев все работы, мы получим [math]S_{n}[/math] — множество работ, которые мы успеваем выполнить до наступления их дедлайнов, причем вес просроченных работ будет наименьшим. От порядка выполнения просроченных работ ничего не зависит, поэтому расположить в расписании их можно произвольным образом.

Псевдокод

Предполагаем, что перед началом выполнения алгоритма выполняется, что [math]m \leqslant d_{1} \leqslant d_{2} \leqslant ... \leqslant d_{n}[/math]. Все работы, дедлайн которых меньше [math]m[/math], мы в любом случае выполнить без штрафа не успеем, поэтому их изначально можно отнести к просроченным.

[math]S[/math] — множество непросроченных работ, [math]Check[/math] — функция, решающая задачу [math] O \mid p_{i,j} = 1, d_i \mid - [/math].

S =  [math]\varnothing[/math]
for i = 1 to n
   S = [math] S \cup \{i\} [/math]
   if not Check(s) :
       найти такое [math]k[/math], что [math]w_{k} = \min \{ w_{j} \mid j \in S\}[/math]
       S = [math]S \setminus \{k\}[/math]

Доказательство корректности

Утверждение:
Алгоритм строит корректное расписание.
[math]\triangleright[/math]
Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества [math] S [/math] на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу [math] k [/math] на работу [math] i [/math]. Но [math] d_{k} \leqslant d_{i} [/math], следовательно, если мы успевали выполнить работу [math] k [/math], то успеем выполнить и работу [math] i [/math].
[math]\triangleleft[/math]
Теорема:
Построенное данным алгоритмом расписание оптимально.
Доказательство:
[math]\triangleright[/math]

Пусть [math] S^* [/math] множество непросроченных работ в оптимальном расписании. Также пусть [math] l [/math] — первая работа из множества [math] S [/math], которая не входит в [math] S^* [/math], а [math] k [/math] — первая работа из [math] S^* [/math], не содержащаяся в [math] S [/math]. Мы можем предполагать существование этих работ, потому что [math] S^* [/math] не может содержать [math] S [/math] как подмножество, иначе это противоречило бы построению [math] S [/math]. С другой стороны, если [math] S^* \subseteq S [/math], то [math] S [/math] должно быть тоже оптимальным, и правильность алгоритма доказана.

Для доказательства покажем, что мы можем заменить работу [math] k [/math] на работу [math] l [/math] в оптимальном расписании, не увеличивая минимизируемую функцию.

Рассмотрим два случая:

  • [math] l \lt k [/math]

Так как работа [math] k [/math] не содержится в [math] S [/math], то либо она не была добавлена при ее рассмотрении, либо была заменена работой, рассмотренной позднее. В любом случае это означает, что [math] w_{k} \leqslant w_{l} [/math]. Так же по определению [math] k [/math] все работы [math] i \in S^* : i \lt k [/math] должны содержаться и в [math] S [/math]. Но тогда заменив в оптимальном расписании [math] k [/math] на [math] l [/math], мы сохраним корректность расписания и не увеличим минимизируемую функцию.

  • [math] k \lt l [/math]

Так как мы рассматриваем работы в порядке неубывания их дедлайнов, то, следовательно, [math] d_{k} \leqslant d_{l} [/math], и замена работы [math] k [/math] на [math] l [/math] в оптимальном расписании [math] S^* [/math] не может сделать его некорректным. Тогда для доказательства нам осталось показать, что [math] w_{k} \leqslant w_{l} [/math].

Пусть [math] k_{i_{0}} = k [/math] — работа, замененная работой [math] i_{0} [/math] в процессе построения [math] S [/math], и пусть [math] k_{i_{1}}, ..., k_{i_{r}} [/math] — последовательность работ, которые были исключены из [math] S [/math] после замены [math] k [/math], причем работа [math] k_{i_{v}} [/math] была заменена работой [math] i_{v} [/math]. [math] i_{0} \lt i_{1} \lt ... \lt i_{r} [/math]. Будем говорить, что "работа [math] i_{v} [/math] подавляет [math] i_{m} [/math]", где [math] m \lt v [/math], если [math] k_{i_{v}} \leqslant i_{m} [/math]. В таком случае получаем, что [math] w_{k_{i_{v}}} \geqslant w_{k_{i_{m}}}[/math], потому что в противном случае работа [math] k_{i_{v}} [/math] была бы исключена из [math] S [/math] раньше чем [math] k_{i_{m}} [/math].

Если в последовательности [math] i_{0} \lt i_{1} \lt ... \lt i_{r} [/math] существует подпоследовательность [math] j_{0} = i_{0} \lt j_{1} \lt ... \lt j_{s} [/math] такая, что [math] j_{v + 1} [/math] подавляет [math] j_{v} [/math] для всех [math] v = 0,1, ..., s - 1 [/math] и [math] j_{s - 1} \lt l \leqslant j_{s} [/math], то получаем, что [math] w_{l} \geqslant w_{k_{j_{s}}} \geqslant ... \geqslant w_{k_{j_{0}}} = w_{k} [/math], что доказывает оптимальность расписания [math] S [/math].

Покажем, что отсутствие такой подпоследовательности приведет нас к противоречию, из чего будет следовать ее существование.

Предположим, что такой подпоследовательности не существует. Тогда найдем наименьшее [math] t [/math] такое, что не существует работы [math] i_{v} : v \gt t [/math], которая бы подавляла работу [math] i_{t} [/math], и [math] i_{t} [/math] было бы меньше [math] l [/math]. По определению [math] l [/math] и [math] i_{t} [/math] и из факта, что [math] i_{t} \lt l [/math], получаем, что после добавления во множество [math] S [/math] работы [math] i_{t} [/math], ни одна из работ, рассмотренных ранее, не будет удалена из [math] S [/math], а так же все эти работы содержатся и в оптимальном расписании [math] S^* [/math], поскольку [math] i_t \lt l [/math].

Пусть [math] S_t [/math] это множество [math] S [/math] после замены работы [math] k_{i_t} [/math] на [math] i_t [/math]. Если [math] k_{i_t} \gt k [/math], то в оптимальном расписании [math] S^* [/math] мы можем заменить работу [math] k [/math] на [math] k_{i_t} [/math], поскольку [math] d_{k_{i_t}} \geqslant d_k [/math]. Но так как [math] S_t \subset S^* [/math], то все работы из множества [math] S_t \cup \{k_{i_t}\} [/math] могут быть выполнены до их дедлайнов, что противоречит построению [math] S [/math]. Следовательно, [math] k_{i_t} \lt k [/math]. Тогда аналогично предыдущему случаю получаем, что все работы из множества [math] S_t \cup \{k\} [/math] могут быть выполнены вовремя. Кроме того, все работы из [math] \{ j \in S_t | j \lt k \} \cup \{k_{i_t}\} [/math] так же могут быть выполнены вовремя, что следует из построения [math] S_t [/math]. Но тогда получается, что все работы и из множества [math] S_t \cup \{k_{i_t}\} [/math] так же могут быть выполнены вовремя, что опять приводит нас к противоречию с построением [math] S [/math].
[math]\triangleleft[/math]

Время работы

Время работы зависит от того, на сколько быстро мы будем добавлять, находить и удалять работы из множества [math]S[/math]. В качестве [math]S[/math] можно использовать двоичную кучу или красно-черное дерево и тогда все нужные нам операции будут выполняться за [math]O(\log n)[/math]. Тогда время алгоритма будет [math]O(n*(\log n + T(Check)))[/math]. Так как [math]T(Check)=O(nm)[/math], то время алгоритма [math]O(n^2*m)[/math]

См. также

Источники информации