Изменения
Нет описания правки
*<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> p_i </tex> {{---}} время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> {{---}} скорость работы <tex> j </tex>-oй машины.
Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots T]</tex>:
</tex>
Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>.
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>\mathrm{level}</tex>-алгоритма.
===Псевдокод===
Функция <tex>\mathrm{level}</tex> принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.
'''function''' level(p : '''int[n]''', s : '''int[m]''', n : '''int''', m : '''int''') : '''vector<int, int, int, int>'''
'''vector<int, int, int, int>''' ans
'''int''' t = 0
'''int''' k = n <font color=green> // количество еще не выполненных работ </font>
sort(p) <font color=green> // сортируем время обработки работ по убыванию </font>
sort(s) <font color=green> // сортируем станки по убыванию скоростей </font>
'''int[]''' to = assign(p, k, m) <font color=green> // получаем распределение работ по станкам </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) <font color=green> // то есть такое минимальное время, через которое, </font> <font color=green> // оставшийся объем каких-нибудь двух работ сравняется </font>
'''int''' dt = min(dt1, dt2)
'''for''' j = 0 '''to''' n - 1
Функция <tex>\mathrm{assign}</tex> принимает на вход массив с объемами работ и возвращает массив с распределением работ.
'''function''' assign (p : '''int[n]''', n k : '''int''', m : '''int''') : '''int[]''' '''int[n]''' to <font color=green> // j работа обрабатывается на to[j] станке </font>
fill(to, -1)
'''set<int>''' s <font color=green> // множество уже распределенных работ </font>
'''int''' i = 0
'''while''' i < m '''and''' i < nk Находим первый j такой что p[j] максимальныйи s не содержит j s.add(j)
m[j] = i++
'''return''' to
Предположим, что <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \leqslant i \leqslant m-1 </tex>. Тогда <tex>\mathrm{level}</tex> последней работы, выполнявшейся на станке <tex> M_i </tex> в момент времени <tex> f_i - \varepsilon </tex> (где <tex> \varepsilon > 0</tex> достаточно мал) меньше, чем <tex>\mathrm{level}</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию, так как при распределении, работы с наибольшим <tex>\mathrm{level}</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>.
}}
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 124 {{---}} 129 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]
[[Категория: Теория расписаний]]
