<tex dpi = "200"> P \mid p_i=1; r_i - integer \mid L_{max} </tex>
{{Задача
|definition=
Дано <tex>m</tex> однородных станков, работающих параллельно, и <tex>n</tex> работ с временем выполнения <tex>p_i = 1</tex>, временем появления <tex>r_i</tex>, заданным целым числом, и момент времени <tex>d_i</tex>, к которому нужно выполнить работу. Необходимо построить такое расписание, чтобы значение максимального опоздания <tex>L_{max} = \max\limits_{i=1\ldots n} (C_i - d_i)</tex> было минимальным.
}}
== Описание алгоритма ==
=== Идея ===
Отсортируем все работы по времени появления в неубывающем порядке так, что <tex>r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>. Теперь будем выполнять доступные на данный момент работы в порядке неубывания дедлайнов <tex>d_i</tex>. То есть, если в момент времени <tex>t</tex> есть свободные станки и есть невыполненные работы такие, что <tex>r_i \leqslant t</tex>, то назначаем работу с наименьшим дедлайном <tex>d_i</tex> на свободный станок.

=== Псевдокод ===
Алгоритм принимает на вход массив пар, где первый элемент является временем появления <tex>r_i</tex> работы, а второй её дедлайном <tex>d_i</tex>, и возвращает расписание, представленное массивом, где на позиции <tex>i</tex> стоит момент обработки работы <tex>i</tex>.

'''function''' scheduling(jobs: '''<int, int>'''[n]) -> '''int[n]'''
sort(jobs) // сортируем работы в порядке неубывания времени появления
'''int''' j = 1 // последняя невыполненная работа
'''int[n]''' ans // массив, куда будет записано расписание
'''heap''' M // куча, в которой будем хранить доступные на данный момент работы в порядке неубывания дедлайнов
'''while''' j <= n
'''int''' time = jobs[j].first // время начала выполнения текущего блока работ
'''while''' jobs[j].first <= time // добавляем в кучу все невыполненные работы, доступные на данный момент
M.push(j)
j++

'''int''' k = 0 // количество занятых станков в данный момент времени
'''while''' M.notEmpty()
i = M.pop() // получаем доступную работу с наименьшим дедлайном 
ans[i] = t // назначаем работу i на время t
'''if''' k + 1 < m // если в момент t есть свободный станок, то назначаем работу i на него
k++
'''else''' // иначе увеличиваем время и обновляем список доступных работ
t++
k = 0
'''while''' jobs[j].first <= time
M.push(j)
j++

Внутренний цикл '''while''' распределяет работы блоками, в которых они выполняются без простоя станков. После окончания такого блока, время начала выполнения следующего будет равно текущему значению <tex>r_j</tex>.
=== Асимптотика ===
Сначала мы сортируем работы, что занимает <tex> \mathcal{O}(n\log{n})</tex>. Далее идёт цикл, в котором мы <tex>n</tex> раз кладём элемент в кучу и <tex>n</tex> раз извлекаем, что также занимает <tex> \mathcal{O}(n\log{n})</tex> времени. В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n})</tex>.

== Доказательство корректности алгоритма ==
{{Теорема
|statement=
Приведенный алгоритм строит оптимальное расписание для задачи <tex> P \mid p_i=1; r_i - integer \mid L_{max} </tex>.
|proof=
Пусть <tex>S</tex> {{---}} расписание построенное предложенным алгоритмом, а <tex>S^*</tex> оптимальное расписание со следующими свойствами:
* первые <tex>r-1</tex> работ из <tex>S</tex> в обоих расписаниях назначены на одно и тоже время и
* значение <tex>r-1</tex> {{---}} наибольшее.
Таким образом работа <tex>J_r</tex> в расписании <tex>S</tex> назначена на время <tex>t</tex>, а в расписании <tex>S^*</tex> на другой более поздний момент времени. Если в момент времени <tex>t</tex> в расписании <tex>S^*</tex> есть свободный станок, то работа <tex>J_r</tex> может быть назначена на этот станок и выполнена в момент <tex>t</tex>. Иначе существует работа <tex>J_k</tex> такая, что <tex>d_r \leqslant d_k</tex>, которая выполнится в расписании <tex>S^*</tex> в момент <tex>t</tex>, а в <tex>S</tex> в другое время. Тогда мы меняем местами работы <tex>J_k</tex> и <tex>J_r</tex> в расписании <tex>S^*</tex>, что не нарушает оптимальность <tex>S^*</tex>, но является противоречием максимальности значения <tex>r-1</tex>.
}}

== См. также ==
* [[Pintreepi1Lmax|<tex>P \mid intree, p_{i} = 1 \mid L_{max}</tex>]]
* [[PpmtnriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]]

== Источники информации ==
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 111-112 ISBN 978-3-540-69515-8

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Теория расписаний]]

QpmtnSumCi

2016-05-29T22:07:11Z

46.183.217.186: лемма

<tex dpi = "200"> Q \mid pmtn \mid \sum C_i </tex>
{{Задача
|definition=
Дано <tex>m</tex> станков с разной скоростью выполнения работ <tex>v_j</tex> и <tex>n</tex> работ с заданным временем выполнения <tex>p_i</tex>. Работы можно прерывать и продолжать их выполнение на другом станке. Необходимо построить такое расписание, чтобы суммарное время окончания всех работ было минимальным.
}}
== Описание алгоритма ==
[[Файл:QpmtnSumCi example.png|320px|thumb|right|Пример работы алгоритма]]
=== Идея ===
Для решения применим правило '''SRPT-FM''' (Shortest Remaining Processing Time on Fastest Machine), которое предлагает класть работу с наименьшим оставшемся временем обработки на самый быстрый доступный станок. Отсортируем работы по времени обработки в невозрастающем порядке так, что <tex>p_1 \ge p_2 \ge ... \ge p_n</tex>. Отсортируем станки по скорости обработки в невозрастающем порядке, так чтобы <tex>v_1 \ge v_2 \ge ... \ge v_m</tex>. Далее назначаем <tex>n</tex>-ю работу на станок <tex>M_1</tex> (1-й по скорости станок) на время <tex>t_1 = \cfrac{p_n}{v_1}</tex>, то есть пока она полностью не выполнится. Теперь назначим <tex>n-1</tex> работу сначала станок <tex>M_2</tex> на время <tex>t_1</tex>, а затем на время от <tex>t_1</tex> до <tex>t_2 \ge t_1</tex> на станок <tex>M_1</tex>, пока она не завершится. С <tex>n-2</tex> работой поступаем аналогично, сначала она <tex>t_1</tex> времени выполняется на станке <tex>M_3</tex>, затем <tex>t_2 - t_1</tex> времени на станке <tex>M_2</tex>, и, начиная с <tex>t_2</tex> до <tex>t_3 \ge t_2</tex>, на станке <tex>M_1</tex>. Также поступаем со всеми оставшимися работами.

=== Псевдокод ===
a = 0
p[] // массив времен обработки работ отсортированный в невозрастающем порядке
v[] // массив скоростей обработки станков отсортированный в невозрастающем порядке
'''while''' p[1] > 0
Находим наибольший i такой, что p[i] > 0
t = p[i] / v[1]
'''for''' j = i '''down to''' k = max(1, i - m + 1)
Назначаем работу j на станок <tex>M_{1+i-j}</tex> на время от a до a + t
p[j] = p[j] - t * v[1 + i - j]
a = a + t

Сложность алгоритма составляет <tex> \mathcal{O}(n\log{n} + mn)</tex>.

== Доказательство корректности алгоритма ==
{{Лемма
|statement=
Существует оптимальное расписание, в котором <tex>C_j \le C_k</tex>, когда <tex>p_j \le p_k</tex>, для всех <tex>j</tex> и <tex>k</tex>
|proof=
Рассмотрим расписание <tex>S</tex>, где для некоторых <tex>j</tex> и <tex>k</tex> верно, что <tex>C_j > C_k</tex>, но <tex>p_j \le p_k</tex>. С помощью обмена частей обработки, полученной работами <tex>j</tex> и <tex>k</tex>, мы можем изменить расписание <tex>S</tex>, получив новое оптимальное расписание <tex>S'</tex>, где обработка работ <tex>j</tex> и <tex>k</tex> завершается во времена <tex>C'_j \le C_k</tex> и <tex>C'_k = C_j</tex> соответственно, при этом время завершения обработки остальных работ остается прежним. Тот факт, что в расписании <tex>S'</tex> работа <tex>j</tex> заканчивается раньше <tex>k</tex>, при этом не нарушая оптимальности расписания, свидетельствует о существовании расписания, описанного в условии леммы.

Для построения расписания <tex>S'</tex> из расписания <tex>S</tex> введем следующие обозначения:
* <tex>p^1_j</tex>, <tex>p^1_k</tex> {{---}} количество обработки, полученной одновременно <tex>j</tex> и <tex>k</tex>, когда работа <tex>j</tex> была на более быстром станке или обе работы были на одинаковых станках.
* <tex>p^2_j</tex>, <tex>p^2_k</tex> {{---}} количество обработки, полученной одновременно <tex>j</tex> и <tex>k</tex>, когда работа <tex>k</tex> была на более быстром станке.
* <tex>p^3_j</tex>, <tex>p^3_k</tex> {{---}} количество обработки, полученной <tex>j</tex> и <tex>k</tex> до момента <tex>C_k</tex> на непересекающихся участках времени.
* <tex>p^+_j</tex> {{---}} количество обработки, полученной <tex>j</tex> после момента <tex>C_k</tex>.

Далее существуют два случая:
* Если <tex>p^+_j \le p^3_k</tex>, то расписание <tex>S'</tex> получается обменом обработки, полученной <tex>j</tex> после момента <tex>C_k</tex> с частью обработки, полученной <tex>k</tex> не одновременно с <tex>j</tex>.
* Если <tex>p^+_j > p^3_k</tex>, то для начала обмениваем всю обработку <tex>p^3_k</tex> с частью <tex>p^+_j</tex>, чтобы получить новое расписании, где <tex>C'_k = C_j</tex> и <tex>\tilde{p}^+_j = p^+_j - p^3_k</tex> обработки <tex>j</tex> после момента <tex>C_k</tex>. Пусть <tex>p^2_j</tex> и <tex>p^2_k</tex> представлены числом <tex>T</tex> непересекающихся временных интервалов длинной <tex>t_i</tex> с <tex>v^i_j</tex>, <tex>v^i_k</tex> {{---}} скоростями станков, обрабатывающих <tex>j</tex> и <tex>k</tex> в интервал <tex>i</tex> и <tex>p^{2,i}_j = v^i_j \cdot t_i</tex>, <tex>p^{2,i}_k = v^i_k \cdot t_i</tex> {{---}} количество обработки, полученной соответвующей задачей за этот интервал. Так как <tex>p^1_j \ge p^1_k</tex> и <tex>p_j \le p_k</tex>, то <tex>p^2_j + \tilde{p}^+_j \le p^2_k</tex>. Следовательно существует такой <tex>\tilde{p}^{+,i}_j</tex>, что верно: <tex>\sum\limits_{i=1}^{T}{\tilde{p}^{+,i}_j} = \tilde{p}^+_j</tex>, <tex>p^{2,i}_j + \tilde{p}^{+,i}_j \le p^{2,i}_k</tex>, <tex>i = 1...T</tex> Для каждого <tex>i = 1...T</tex> пусть <tex>t^i_j = \cfrac{\tilde{p}^{+,i}_j}{v^i_k - v^i_j}</tex>, <tex>t^i_k = t^i_j \cdot \cfrac{v^i_j}{v^i_k}</tex>. Чтобы получить расписание <tex>S'</tex> для каждого из <tex>T</tex> интервалов нужно обменять: 1) обработку, полученную в начале интервала работой <tex>k</tex> на более быстром станке, с обработкой <tex>j</tex>, полученной на медленном станке, на интервалы <tex>t^i_k</tex> и <tex>t^i_j</tex> соответственно 2) обработку <tex>\tilde{p}^{+,i}_j</tex>, полученной <tex>j</tex> после момента <tex>C_k</tex>, с таким же количеством обработки, полученной работой <tex>k</tex> на более быстром станке в этот интервал сразу после момента <tex>t^i_k</tex>.
}}

{{Теорема
|statement=
Расписание, построенное по принципу '''SRPT-FM''', оптимальное для задачи <tex> Q \mid pmtn \mid \sum C_i </tex>
|proof=
В разработке
}}