1632
правки
Изменения
м
Цель *<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> станков
1. Найдем нижнюю границу времени Необходимое условие для выполнения.всех работ в интервале <tex>[0 \ldots T]</tex>:
2. Составим оптимальное расписание.<tex> P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT</tex> или <tex>\dfrac{P_n}{S_m} \leqslant T</tex>
Где Далее построим расписание, которое достигает нашей оценки <tex>i = 1 ... nC_{max}</tex>; , с помощью <tex>j = 1 ... m</tex>; <tex> p_i\mathrm{level}</tex> - вес i-ой работы ;<tex> s_j</tex> - скорость работы j-oй машины ; <tex> n \ge m</tex>;алгоритма.
Необходимое условие для выполнения всех ===Псевдокод===Функция <tex>\mathrm{level}</tex> принимает на вход два массива — массив с объемами работ в интервале и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке. '''function''' level(p : '''int[n]''', s : '''int[m]''') : '''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> '''while''' k > 0 '''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> // оставшийся объем каких-нибудь двух работ сравняется <tex/font> '''int''' dt = min(dt1, dt2) '''for''' j = 0 '''to''' n - 1 '''if''' p[j] > 0;T '''if''' to[j]<tex> \neq </tex>:-1 <font color=green> // рассматриваем работы которые обрабатываются в данном распределении</font> ans.push(to[j], j, t, t + dt) p[j] -= s[to[i]] * dt '''if''' p[j] == 0 k-- t += dt <font color=green> // поиск следующего момента времени, в который нужно будет перераспределить машины/работы </font> '''return''' ans
Нижняя граница ===Асимптотика===<tex>C_\mathrm{maxlevel}</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>w = \max\{\max\limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}</tex>
Будем назвать Level-ом работы ===Доказательство корректности алгоритма==={{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.|proof=Так как нижняя граница <tex> lvl(p_i(t)) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t C_{max}</tex>:
Далее построим расписание, которое достигает нашей оценки <tex>wC_{max} = \max\left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\\max\limits_{j=1 \ldots m-1} \dfrac{P_j}{S_j} \end{array} \right. </tex>, с помощью Level-алгоритма.
Level - алгоритм:то достаточно показать, что составленное расписание достигает этой оценки.
Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <tex>t p_1(0) \leftarrow geqslant p_2(0 </tex> '''WHILE''' существуют работы с положительным level Assign(t) <tex>t1 \leftarrow mingeqslant \ldots \geqslant p_n(s>t |0) </tex>работа выполненная в момент . Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени . Получаем: <tex> sp_1(t)</tex> <tex>t2 \leftarrow min(s>t | p_igeqslant p_2(t)>p_j\geqslant \ldots \geqslant p_n(t)</tex> && . Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени <tex> p_i(s) == p_j(s))T</tex> <tex> t \leftarrow min(t1нет простоев машин,t2) </tex> Построение расписаниякогда есть хотя бы одна невыполненная работа. Получаем:
Функция <tex>Assign T(ts_1 + \ldots + s_m)= p_1 + p_2 + \ldots + p_n </tex> или <tex> T = \dfrac{P_n}{S_m} </tex>:
<tex>Levels = \{i|p_i(t)>0\}</tex> <tex>M = \{M_1,Таким образом необходимая оценка достигается нашим алгоритмом...,M_m\}</tex> - множество всех станков '''WHILE''' (<tex>Levels</tex> != 0 && <tex>M</tex> != 0) Найти множество работ <tex>I</tex> подмножество <tex>Levels</tex> ,level которых максимальный <tex>r \leftarrow min</tex>(|<tex>M</tex>|,|<tex>I</tex>|) Назначаем работы из мн-ва <tex>I</tex> на <tex>r</tex> самых быстрых машин из мн-ва <tex>M</tex> <tex>Levels \leftarrow Levels</tex>\<tex>I</tex> удаляем из мн-ва <tex>M</tex> <tex>r</tex> самых быстрых машин
==Доказательство корректности алгоритма==Так Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как нижняя граница <tex>C_{max}f_i </tex>) на станках <tex>M_1 \ldots M_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>. Докажем что алгоритм составляет расписание в соответствии с этим свойством. Чтобы доказать этот факт, будем считать что в любой момент времени T нет простоев машин, когда есть хотя бы одна невыполненная работа. Получаемнаписанное выше неравенство: <tex> T(s_1 + ... + s_m) = p_1 + p_2 + ... + p_n </tex> или <tex> T = {P_n \over S_n} </tex> Таким образом необходимая оценка достигается нашим алгоритмом.
Допустим хотя бы одна машина простаиваетПредположим, что <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_1 M_{i+1} </tex>... M_mПришли к противоречию, так как при распределении, работы с наибольшим <tex>\mathrm{level}</tex>:выставлялись на самые быстрые станки.
В этом случае, если <tex> f_i < f_{i+1} </tex> для некоторого <tex> 1 \le i \le m-1 </tex>, Level последней работы выполнявшейся на станке <tex> M_i </tex> равен <tex> f_i - \varepsilon </tex>===Пример===[[Файл:Qpmtncmax. Где <tex> \varepsilon > 0</tex> достаточно мал, и меньше чем Level последней работы на станке <tex> M_{i+1} </tex>. Пришли png|600px|thumb|right|Картинка к противоречию.примеру]]
==Пример==[[Файл:qptmncmaxПусть у нас есть <tex>6</tex> работ и <tex>3</tex> станка. Покажем работу алгоритма для данного случая.png|400px|thumb|right|Картинка к примеру]]
Пусть у нас есть 5 работ В начальный момент времени начинаем обрабатывать работы с наибольшим временем выполнения <tex>J_1</tex>, <tex>J_2</tex> и 4 станка<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>J_1-J_4</tex> на станках <tex>M_1-M_4</tex> соответственно==См. В момент времени также==* [[QpmtnSumCi|<tex>t_1Q \mid pmtn \mid \sum C_i</tex> <tex>lvl</tex> 4-ой работы опускается до времени выполнения 5-ой работы. С этого момента начинаем обрабатывать работы <tex> J_4,J_5</tex> на одном станке: <tex>M_4</tex>. В момент времени <tex>t_2</tex> происходит похожая ситуация. С этого момента времени работы <tex> J_1,J_2</tex> выполняются синхронно на двух станках <tex> M_1,M_2</tex>. Далее работы не пересекаются друг с другом и каждая заканчивается на ранее выделенных им станках.]]
==Литература==[[Категория: Алгоритмы и структуры данных]]* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8[[Категория: Теория расписаний]]
rollbackEdits.php mass rollback
<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> работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.}}
==Постановка задачиАлгоритм построения расписания==Есть несколько станков с разной скоростью ===Описание алгоритма===Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения работ. Работу на каждом из станков можно прервать и продолжить позже:<tex> p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n</tex>, а все машины в порядке убывания скоростей: <tex> s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m</tex>. Введем следующие обозначения:
Кроме того, должно выполняться условие <tex>\dfrac{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> P_i C_{max} = p_1 + ..\max\left \{\begin{array}{ll} \dfrac{P_n}{S_m} \\\max\limits_{j=1 \ldots m-1} \dfrac{P_j}{S_j} \end{array} \right. + p_i</tex>
Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> S_j = s_1 + ... + s_jp_i </tex> в момент времени <tex> t </tex>.
Функция <tex> P_n = p_1 + ... + p_n \le s_1T + mathrm{assign}</tex> принимает на вход массив с объемами работ и возвращает массив с распределением работ... + s_mT '''function''' assign(p : '''int[n]''', k : '''int''', m : '''int''') : '''int[]''' '''int[n]''' to <font color= S_mTgreen> // j работа обрабатывается на to[j] станке </texfont> fill(to, -1) '''set<int> или ''' s <texfont color=green>P_n/S_m \le T/ множество уже распределенных работ </texfont> '''int''' i = 0 '''while''' i < m '''and''' i < k Находим первый j такой что p[j] максимальный и s не содержит j s.add(j) m[j] = i++ '''return''' to
<tex>w = f_1 \maxgeqslant f_2 \{geqslant \maxldots \limits_{j=1}^{m-1} {P_i \over S_j}, {P_n \over S_m}\}geqslant f_m </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 \ge f_2 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 \ge varepsilon < T - t </tex>.Таким образом, до момента времени <tex> T </tex> нет простаивающих машин.Пришли к противоречию. Получаем <tex> T = \ge f_m dfrac{P_j}{S_j} </tex>.}}
==Время работыИсточники информации==Level* Peter Brucker. «Scheduling Algorithms» {{-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз--}} «Springer», 2006 г. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>{{---}} 124 {{---}} 129 стр.{{---}} ISBN 978-3-540-69515-8
