Изменения
Нет описания правки
<div styletex dpi ="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;200">Эта статья находится в разработке!Q \mid pmtn \mid C_{max}</divtex>{{Задача|definition=Дано <includeonlytex>[[Категория: В разработке]]m</includeonlytex> ==Постановка задачи==Есть несколько станков с разной скоростью выполнения работ, работающих параллельно, и <tex>n</tex> работ. Работу на каждом из станков можно прервать Работа может быть прервана в любой момент и продолжить продолжена позжена любой машине. Цель - выполнить все как можно быстрее. 1. Найдем нижнюю границу времени Необходимо минимизировать время выполнениявсех работ. 2. Составим оптимальное расписание.}}
==Алгоритм построения расписания==
===Описание алгоритма===Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеиявыполнения:<tex> p_1 \ge geqslant p_2 \ge geqslant p_3... \ldots \geqslant p_n</tex>, а все машины в порядке убывания скоростей: <tex> s_1 \ge geqslant s_2 \ge geqslant s_3 ... \ldots \geqslant s_m</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> S_j = s_1 + ... + s_j[0 \ldots T]</tex>:
<tex> P_n C_{max} = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>max\left \{\begin{array}{ll} \dfrac{P_n/}{S_m } \\\le Tmax\limits_{j=1 \ldots m-1} \dfrac{P_j}{S_j} \end{array} \right. </tex>
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex> = , с помощью <tex>\max\mathrm{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\level}</tex>-алгоритма.
===Асимптотика===<tex>Level\mathrm{level}</tex> - алгоритм:вызывает функцию <tex>\mathrm{assign}(t) </tex> в самом худшем случае <tex>O(n)</tex> раз. Функция <tex>\mathrm{assign}(t) </tex> выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.
то достаточно показать, что составленное расписание достигает этой оценки.
Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \ge geqslant p_2(0) \ge ... geqslant \ldots \ge geqslant p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge geqslant p_2(t) \ge ... geqslant \ldots \ge 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>
Таким образом необходимая оценка достигается нашим алгоритмом.
Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 ... \ldots M_m</tex>, пронумерованных по убыванию скоростей:
<tex> f_1 \ge geqslant f_2 \ge ... geqslant \ge ldots \geqslant f_m </tex>
Докажем написанное выше неравенство:
Предположим, что <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le leqslant i \le 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>\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) \ge geqslant p_2(0) \ge ... geqslant \ldots \ge geqslant p_m(0) \ge geqslant p_i(0) </tex>, из чего следует, что <tex> p_1(T - \varepsilon) \ge ... geqslant \ldots \ge geqslant p_m(T - \varepsilon) \ge geqslant p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex>, удовлетворяющего условию <tex> 0 \le leqslant \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Пришли к противоречию. Получаем <tex> T = \dfrac{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>\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>, и все работы закончатся одновременно.
==Время работыИсточники информации==<tex> Level </tex> * Peter Brucker. «Scheduling Algorithms» {{- алгоритм вызывает функцию <tex> Assign(t) </tex> в самом худшем случае <tex>O(n)</tex> раз--}} «Springer», 2006 г. Функция <tex> Assign(t) </tex> выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>{{---}} 124 {{---}} 129 стр.{{---}} ISBN 978-3-540-69515-8