Изменения
Нет описания правки
}}
<tex> P_i = p_1 + \ldots + p_i</tex>
<tex> S_j = s_1 + \ldots + s_j</tex>
<tex>i = 1 \ldots n</tex>, <tex>j = 1 \ldots m</tex>, <tex> p_i</tex> {{- --}} время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> {{--- }} скорость работы <tex> j </tex>-oй машины.
Необходимое условие для выполнения всех работ в интервале <tex>[0..T]</tex>:
Кроме того, должно выполняться условие <tex>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}</tex> = <tex>\max\left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\\max\limits_{j=1}^{\ldots m-1} \dfrac{P_j \over }{S_j}, \end{P_n \over S_marray}\}right. </tex>
Перейдем к описанию алгоритма. Будем назвать <tex>Level\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level\mathrm{level}</tex>-алгоритма.
===Псевдокод===Функция <tex>Level\mathrm{level}</tex> - алгоритм: '''function''' level(): '''int''' <tex>t = 0 </tex> '''while''' <tex>\exists p(t) > 0</tex> assign(t) '''int''' <tex>t_1 = \min (s \mid s > t </tex> '''and''' <tex>p(s) = 0)</tex> '''int''' <tex>t_2 = \min (s \mid s > t</tex> '''and''' <tex>\exists i</tex>, <tex>j : p_i(t) > p_j(t)</tex> '''and''' <tex>p_i(s) = p_j(s))</tex> <tex>t = \min(t_1</tex>, <tex>t_2)</tex> <font color=green> // поиск следующего момента времени, в который нужно будет перераспределить машины/работы </font> Построение расписания
===Доказательство корректности алгоритма===
{{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.|proof=Так как нижняя граница <tex>C_{max}</tex>:
<tex>C_{max}</tex> = <tex>\max\left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\\max\limits_{j=1}^{\ldots m-1} \dfrac{P_j \over }{S_j}, \end{P_n \over S_marray}\}right. </tex>
то достаточно показать, что составленное расписание достигает этой оценки.
Докажем написанное выше неравенство:
Предположим, что <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \leqslant i \leqslant m-1 </tex>. Тогда <tex>Level\mathrm{level}</tex> последней работы, выполнявшейся на станке <tex> M_i </tex> в момент времени <tex> f_i - \varepsilon </tex> (где <tex> \varepsilon > 0</tex> достаточно мал) меньше, чем <tex>Level\mathrm{level}</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию, так как при распределении, работы с наибольшим <tex>Level\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 = {P_j \over S_j} </tex>.
}}
===Пример===
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]
Пусть у нас есть <tex>6 </tex> работ и <tex>3 </tex> станка. Покажем работу алгоритма для данного случая.
В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-</tex>, <tex>J_2</tex> и <tex>J_3</tex> на станках <tex>M_1-</tex>, <tex>M_2</tex> и <tex>M_3</tex> соответственно. В момент времени <tex>T_1</tex> <tex>lvl\mathrm{level}</tex> <tex> 1</tex>-ой работы и <tex>2</tex>-ой работы совпадает. С этого момента начинаем обрабатывать работы <tex> J_1,</tex> и <tex>J_2</tex> синхронно на станках: <tex>M_1 </tex> и <tex>M_2</tex>. В момент времени <tex>T_2</tex> работа <tex>J_3</tex> опускается до уровня работы <tex>J_4</tex>.Работы <tex> J_3,</tex> и <tex>J_4</tex> выполняем одновременно на одном станке <tex> M_3</tex>. В момент времени <tex>T_3</tex> начинаем выполнять первые четыре работы на всех станках одновременно, далее просто добавятся работы <tex>J_5 </tex> и <tex>J_6</tex> , и все работы закончатся одновременно.
===Время работы=См. также==* [[QpmtnSumCi|<tex> Level Q \mid pmtn \mid \sum C_i</tex> - алгоритм вызывает функцию <tex> Assign(t) </tex> в самом худшем случае <tex>O(n)</tex> раз. Функция <tex> Assign(t) </tex> выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.]]
==Источники информации==
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 124 {{---}} 129 стр. {{---}} ISBN 978-3-540-69515-8
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
