Изменения

Дано несколько <tex>m</tex> станков с разной скоростью выполнения работ, работающих параллельно, и <tex>n</tex> работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.

Пусть нам даны <tex>n</tex> работ и <tex>m</tex> станков. Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения:<tex> p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n</tex>, а все машины в порядке убывания скоростей: <tex> s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m</tex>. Введем следующие обозначения:

*<tex> P_i = p_1 + \ldots + p_i</tex> , <tex> S_j i = s_1 + 1 \ldots + s_jn</tex> {{---}} сумма первых <tex>i = 1 \ldots n</tex>, работ*<tex>j S_j = 1 s_1 + \ldots m+ s_j</tex>, <tex> p_i </tex> {{---}} время выполнения <tex>i</tex>-ой работы, <tex> s_jj = 1 \ldots m</tex> {{---}} скорость работы сумма скоростей первых <tex> j </tex>-oй машины.станков

<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>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>.

Функция <tex>\mathrm{level}</tex>:принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке. '''function''' level()p : '''int[n]''' <tex>t = 0 </tex> , s : '''whileint[m]''' <tex>\exists p(t) > 0: '''vector</texint, int, int, int> assign(t) '''int ''' vector<texint, int, int, int>t_1 = \min (s \mid s > t </tex> '''and''' <tex>p(s) = 0)</tex>ans '''int''' <tex>t_2 t = \min (s \mid s > t</tex> 0 '''andint''' k = n <texfont color=green>\exists i</tex>, <tex>j : p_i(t) > p_j(t)</tex> '''and''' <tex>p_i(s) = p_j(s))количество еще не выполненных работ </texfont> <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> Найдем минимальное dt1 отличное от нуля такое, что (p[i] - s[to[i]] * dt1) = 0 Найдем минимальное dt2 такое, что p[i] > p[j] и (p[i] - s[to[i]] * dt2 = p[j] - s[to[j]] * dt2) <texfont color=green>M = \{M_1 \ldots M_m\}// то есть такое минимальное время, через которое, </texfont> <font color=green> // множество всех станков оставшийся объем каких-нибудь двух работ сравняется </font> '''int''' dt = 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> '' 'int''return' <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> T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n </tex> или <tex> T = \dfrac{P_n \over }{S_m} </tex>

Пусть <tex> T </tex> = <tex> f_1 = f_2 = f_3 = \ldots = f_j > f_{j+1}</tex> ,где <tex> j < m </tex>. Чтобы работы завершились в момент времени <tex> T </tex>, необходимо начать их в момент времени 0, поскольку если это не выполняется, то у нас найдется работа <tex> J_i </tex> , которая начинается позже <tex> t = 0 </tex> и заканчивается в <tex> T </tex>. Это означает, что в момент времени <tex> 0 </tex> начинаются как минимум <tex> m </tex> работ. Пусть первые <tex> m </tex> работ стартовали вместе на всех машинах. Мы получаем <tex> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_m(0) \geqslant p_i(0) </tex>, из чего следует, что <tex> p_1(T - \varepsilon) \geqslant \ldots \geqslant p_m(T - \varepsilon) \geqslant p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex>, удовлетворяющего условию <tex> 0 \leqslant \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Пришли к противоречию. Получаем <tex> T = \dfrac{P_j \over }{S_j} </tex>.

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