Изменения

<tex dpi ==Постановка задачи="200">Q \mid pmtn \mid C_{max}</tex>{{Задача|definition=Есть Дано несколько станков с разной скоростью выполнения работ, работающих параллельно. Работу на каждом из станков можно прервать Работа может быть прервана в любой момент и продолжить продолжена позжена любой машине. Необходимо минимизировать время выполнения всех работ.}}

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

==Алгоритм построения расписания==Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </tex>, а все машины в порядке убывания скоростей: <tex> s_1 \ge s_2 \ge s_3 ... </tex>. Введем следующие обозначения: <tex> P_i = p_1 + ... + p_i</tex> <tex> S_j = s_1 + ... + 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> P_n = p_1 + ... \ldots + p_n \le leqslant s_1T + ... \ldots + s_mT = S_mT</tex> или <tex>P_n/S_m \le leqslant T</tex>

Кроме того, должно выполняться условие <tex>P_j/S_j \le leqslant T</tex> для всех <tex> j = 1..\ldots m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1...\ldots J_j</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</tex> :

'''WHILEwhile''' существуют работы с положительным <tex>level\exists p(t) > 0</tex>

<tex>t1 t_1 \leftarrow \min (s > t \mid s> t </tex> - время окончания какой-то работы '''and''' <tex> p(s) = 0) </tex> <tex>t2 t_2 \leftarrow \min (s \mid s > t \mid </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 \leftarrow \min(t1t_1</tex>,t2<tex>t_2) </tex> <font color=green> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы</font>

<tex>J = \{i \mid p_i(t) > 0\}</tex> - <font color=green> // множество работ с положительным <tex>level</texfont> <tex>M = \{M_1,...,\ldots M_m\}</tex> - <font color=green> // множество всех станков</font> '''WHILEwhile''' множества <tex>J\ne \varnothing</tex> и '''or''' <tex>M\ne \varnothing</tex> не пустые Найти множество работ max <texfont color=green>I \subset // максимальное значение level из J</texfont>, count <texfont color=green>// количество работ с level= max </texfont> которых максимален. <tex>r \leftarrow = min(|M|</tex>(|, <tex>Mcount)</tex>|,| <tex>I\leftarrow \{r</tex>|) Назначаем работы работ из множества <tex>IJ \mid p(t) = max\}</tex> на <tex>M' \leftarrow \{r</tex> самых быстрых машин из множества <tex>M\}</tex> Распределяем работы <tex>J \leftarrow J</tex>\<tex>setminus I</tex> Удаляем из множества <tex>M\leftarrow M \setminus M'</tex> <tex>r</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 = {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</tex> последней работы, выполнявшейся на станке <tex> M_i </tex> в момент времени <tex> f_i - \varepsilon </tex> (где <tex> \varepsilon > 0</tex> достаточно мал) меньше, чем <tex>Level</tex> последней работы на станке <tex> M_{i+1} </tex>. Пришли к противоречию, так как при распределении, работы с наибольшим <tex>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 = {P_j \over S_j} </tex>.

===Пример===

===Время работы===

==ЛитератураИсточники информации==* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 124 {{---}} 129 стр. {{---}} ISBN 978-3-540-69515-8