Участник:Qtr/1

[math] 1 \mid p_{i}=1 \mid \sum\nolimits w_iU_i[/math]

Задача:

Дано [math] n [/math] работ и [math] 1 [/math] станок. Для каждой работы известны её дедлайн [math] d_{i} [/math] и вес [math] w_{i} [/math]. Время выполнения всех работ [math] p_i [/math] равно [math] 1 [/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] с наименьшим весом [math] w_{l} [/math] и заменим ее на работу [math] k + 1 [/math].

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

Псевдокод

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

[math] s [/math] — множество непросроченных работ, [math] t [/math] — текущее время.

Set<int> p1sumwu(int [math]w[n][/math], int [math]d[n][/math]):
  int [math] t = 1[/math]
  Set<int> [math]s[/math] = [math]\{\}[/math]
  for [math] i = 1 [/math] to [math] n [/math]
     [math] s = s \cup \{i\} [/math]
     if [math] d_{i}  \geqslant t [/math]     
        [math] t = t + 1 [/math]
     else
        найти такое [math] k [/math], что [math] w_{k} = \min \{ w_{j} \mid j \in s\} [/math]
        [math] s = s \setminus \{k\} [/math]    
  return [math]s[/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) [/math]. Например, такими структурами данных являются двоичная куча и красно-черное дерево.

Более простой случай

Задачу [math] 1 \mid p_{i}=1 \mid \sum\nolimits U_i[/math] можно решить за [math]O(n)[/math]. Рассмотрим следующий алгоритм. Работы, значение [math]d[/math] у которых больше либо равно [math]n[/math], поместим в конец расписания. Для остальных работ заведём [math]n-1[/math] множество [math]S_{1}, S_{2} \dots S_{n-1}[/math]. В множестве [math]S_{i}[/math] будем хранить номера работ, у которых [math]d = i[/math]. Далее для каждого множества будем по очереди добавлять работы, которые успеваем сделать, в расписание (как в строчках 3-6 предыдущего алгоритма). Те работы, которые не успеваем сделать, добавим в конец расписания. Всего будет выполнено O(n) операций и время работы алгоритма, таким образом, составляет [math]O(n)[/math].

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

• Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 96 стр. — ISBN 978-3-540-69515-8