QpmtnCmax

2012-07-01T18:23:29Z

109.248.7.75:

==Постановка задачи==
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.

Цель - выполнить все как можно быстрее.

1. Найдем нижнюю границу времени выполнения.

2. Составим оптимальное расписание.

==Алгоритм построения расписания==
Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<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 ... n</tex>, <tex>j = 1 ... m</tex>, <tex> p_i</tex> - время выполнения <tex>i</tex>-ой работы, <tex> s_j</tex> - скорость работы <tex> j </tex>-oй машины.

Необходимое условие для выполнения всех работ в интервале <tex>[0..T]</tex>:

<tex> P_n = p_1 + ... + p_n \le s_1T + ... + s_mT = S_mT</tex> или <tex>P_n/S_m \le T</tex>

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

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

Перейдем к описанию алгоритма. Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>

Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.

<tex>Level</tex> - алгоритм:

<tex>t \leftarrow 0 </tex>
'''WHILE''' существуют работы с положительным <tex>level</tex>
Assign(t)
<tex>t1 \leftarrow \min (s > t \mid s</tex> - время окончания какой-то работы <tex> ) </tex>
<tex>t2 \leftarrow \min (s > t \mid </tex> для некоторых работ <tex>i, j : p_i(t) > p_j(t)</tex> и <tex> p_i(s) = p_j(s))</tex>
<tex> t \leftarrow \min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
Построение расписания

Функция <tex>Assign(t)</tex>:

<tex>J </tex> - множество работ с положительным <tex>level</tex>
<tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
'''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
Найти множество работ <tex>I \subset J</tex>, <tex>level</tex> которых максимален.
<tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|)
Назначаем работы из множества <tex>I</tex> на <tex>r</tex> самых быстрых машин из множества <tex>M</tex>
<tex>J \leftarrow J</tex>\<tex>I</tex>
Удаляем из множества <tex>M</tex> <tex>r</tex> самых быстрых машин

==Доказательство корректности алгоритма==
Так как нижняя граница <tex>C_{max}</tex>:

<tex>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>

то достаточно показать, что составленное расписание достигает этой оценки.

Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex> p_1(0) \ge p_2(0) \ge ... \ge p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \ge p_2(t) \ge ... \ge p_n(t) </tex>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex>T</tex> нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаем:

<tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_m} </tex>

Таким образом необходимая оценка достигается нашим алгоритмом.

Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 ... M_m</tex>:

<tex> f_1 \ge f_2 \ge ... \ge f_m </tex>

Докажем написанное выше неравенство:

Предположим, что <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le i \le 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> T </tex> = <tex> f_1 = f_2 = f_3 = ... = 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 p_2(0) \ge ... \ge p_m(0) \ge p_i(0) </tex>, из чего следует, что <tex> p_1(T - \varepsilon) \ge ... \ge p_m(T - \varepsilon) \ge p_i(T - \varepsilon) > 0 </tex> для любого <tex> \varepsilon </tex>, удовлетворяющего условию <tex> 0 \le \varepsilon < T - t </tex>. Таким образом, до момента времени <tex> T </tex> нет простаивающих машин. Пришли к противоречию. Получаем <tex> T = {P_j \over S_j} </tex>.

==Пример==
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]

Пусть у нас есть 6 работ и 3 станка. Покажем работу алгоритма для данного случая.

В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1-J_3</tex> на станках <tex>M_1-M_3</tex> соответственно. В момент времени <tex>T_1</tex> <tex>lvl</tex> 1-ой работы и 2-ой работы совпадает. С этого момента начинаем обрабатывать работы <tex> J_1,J_2</tex> синхронно на станках: <tex>M_1 M_2</tex>. В момент времени <tex>T_2</tex> работа <tex>J_3</tex> опускается до уровня работы <tex>J_4</tex>.Работы <tex> J_3,J_4</tex> выполняем одновременно на одном станке <tex> M_3</tex>. В момент времени <tex>T_3</tex> начинаем выполнять первые четыре работы на всех станках одновременно, далее просто добавятся работы <tex>J_5 J_6</tex> и все работы закончатся одновременно.

==Время работы==
<tex> Level </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 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8

Викиконспекты - Вклад участника [ru]

QpmtnCmax