Изменения
переписан псевдокод
{{Задача
|definition=
Дано несколько <tex>m</tex> станков с разной скоростью выполнения работ, работающих параллельно, и <tex>n</tex> работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.
}}
==Алгоритм построения расписания==
===Описание алгоритма===
*<tex> P_i = p_1 + \ldots + p_i</tex>, <tex>i = 1 \ldots n</tex> {{---}} сумма первых <tex>i</tex> работ*<tex>S_j = s_1 + \ldots + s_j</tex>, <tex>j = 1 \ldots m</tex> {{---}} сумма первых <tex>j</tex> станков
Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots T]</tex>:
<tex> P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT</tex> или <tex>\dfrac{P_n/}{S_m } \leqslant T</tex>
Кроме того, должно выполняться условие <tex>\dfrac{P_j/}{S_j } \leqslant T</tex> для всех <tex> j = 1 \ldots m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1 \ldots J_j</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :
<tex>C_{max} = \max
===Псевдокод===
Функция <tex>\mathrm{level}</tex>:принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке. '''function''' level()p : '''int[]''' <tex>t = 0 </tex> , s : '''whileint[]''' <tex>\exists p(t) > 0</tex> assign(t) , n : '''int''' <tex>t_1 = \min (s \mid s > t </tex> , m : '''andint''' <tex>p(s) = 0): '''vector</texint, int, int, int>''' '''vector<int, int, int, int>''' <tex>t_2 = \min (s \mid s > t</tex> ans '''andint''' <tex>\exists i</tex>, <tex>j : p_i(t) > p_j(t)</tex> = 0 '''andint''' <tex>p_i(s) k = p_j(s))</tex>n <tex>t = \min sort(t_1</tex>, <tex>t_2p)</tex> <font color=green> // поиск следующего момента времени, в который нужно будет перераспределить машины/работы сортируем время обработки работ по убыванию </font> Построение расписания Функция sort(s) <texfont color=green>\mathrm{assign}(t)// сортируем станки по убыванию скоростей </texfont>: '''functionwhile''' assign (<texk >t</tex> : 0 '''int[]'''): <tex>J to = \{i \mid p_iassign(tp, k, m) > 0\}</tex> <font color=green> // множество получаем распределение работ с положительным level по станкам </font> <tex Найдем минимальное dt1 отличное от нуля такое, что (p[i] - s[to[i]] * dt1) = 0 Найдем минимальное dt2 отличное от нуля такое, что p[i] >M p[j] и (p[i] - s[to[i]] * dt2 = \{M_1 \ldots M_m\}</tex> <font colorp[j] - s[to[j]] * dt2) '''int''' dt =green> // множество всех станков </font>min(dt1, dt2) '''for''' j = 0 '''whileto''' <tex>J \ne \varnothing</tex> n - 1 '''orif''' <tex>M \ne \varnothing</texp[j] >0 '''intif''' to[j] <tex>maxLevel = \max(p_i(t) \mid i \in J)neq </tex> -1 <font color=green> // максимальное значение level из J рассматриваем работы которые обрабатываются в данном распределении</font> ans.push(to[j], j, t, t + dt) p[j] -= s[to[i]] * dt '''intif''' <tex>count p[j] == 0 k-- t += J.getCount(maxLevel)</tex> dt <font color=green> // количество работ с level = maxLevel поиск следующего момента времени, в который нужно будет перераспределить машины/работы </font> '''intreturn''' <tex>r = \min(|M|</tex>, <tex>count)</tex> <tex>I \leftarrow \{r</tex> работ из <tex>J \mid p(t) = maxLevel\}</tex> <tex>M' \leftarrow \{r</tex> самых быстрых машин из <tex>M\}</tex> Распределяем работы <tex>J \leftarrow J \setminus I</tex> <tex>M \leftarrow M \setminus M'</tex>ans
Функция <tex>\mathrm{assign}</tex> принимает на вход массив с объемами работ и возвращает массив с распределением работ.
'''function''' assign (p : '''int[]''', n : '''int''', m : '''int''') : '''int[]'''
'''int[]''' to <font color=green> // j работа обрабатывается на to[j] станке </font>
fill(to, -1)
'''int''' i = 0
'''while''' i < m '''and''' i < n
Находим первый j такой что p[j] максимальный
m[j] = i++
'''return''' to
===Асимптотика===
Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \geqslant p_2(t) \geqslant \ldots \geqslant p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex>T</tex> нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:
<tex> T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n </tex> или <tex> T = \dfrac{P_n \over }{S_m} </tex>
Таким образом необходимая оценка достигается нашим алгоритмом.
