QpmtnCmax — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности алгоритма)
(не показано 13 промежуточных версий 6 участников)
Строка 1: Строка 1:
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
+
<tex dpi = "200">Q \mid pmtn \mid C_{max}</tex>
<includeonly>[[Категория: В разработке]]</includeonly>
+
{{Задача
 
+
|definition=
==Постановка задачи==
+
Дано <tex>m</tex> станков с разной скоростью выполнения работ, работающих параллельно, и <tex>n</tex> работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.
Есть несколько станков с разной скоростью выполнения работ. Работу на каждом из станков можно прервать и продолжить позже.  
+
}}
 
 
Цель - выполнить все как можно быстрее.
 
 
 
1. Найдем нижнюю границу времени выполнения.
 
 
 
2. Составим оптимальное расписание.
 
  
 
==Алгоритм построения расписания==
 
==Алгоритм построения расписания==
Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнеия:<tex> p_1 \ge p_2 \ge p_3... </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> 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>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>[0;T]</tex>:
+
Необходимое условие для выполнения всех работ в интервале <tex>[0 \ldots 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_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>P_j/S_j \le T</tex> для всех <tex> j = 1..m - 1 </tex>, так как это нижняя оценка времени выполнения работ <tex> J_1...J_{m-1}</tex>. Исходя из этого получаем нижнюю границу <tex>C_{max}</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>C_{max}</tex> = <tex>\max\{\max\limits_{j=1}^{m-1} {P_j \over S_j}, {P_n \over S_m}\}</tex>
+
<tex>C_{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>
  
Будем назвать <tex>Level</tex>-ом работы <tex> p_i(t) </tex> - невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>
+
Перейдем к описанию алгоритма. Будем назвать <tex>\mathrm{level}</tex>-ом работы <tex> p_i(t) </tex> невыполненную часть работы <tex> p_i </tex> в момент времени <tex> t </tex>.
  
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>Level</tex>-алгоритма.
+
Далее построим расписание, которое достигает нашей оценки <tex>C_{max}</tex>, с помощью <tex>\mathrm{level}</tex>-алгоритма.
  
<tex>Level</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> // оставшийся объем каких-нибудь двух работ сравняется </font>
 +
        '''int''' dt = min(dt1, dt2)
 +
        '''for''' j = 0 '''to''' n - 1
 +
            '''if''' p[j] > 0
 +
              '''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>t \leftarrow 0 </tex>
+
Функция <tex>\mathrm{assign}</tex> принимает на вход массив с объемами работ и возвращает массив с распределением работ.
   '''WHILE''' существуют работы с положительным <tex>level</tex>
+
   '''function''' assign(p : '''int[n]''', k : '''int''', m : '''int''') : '''int[]'''
      Assign(t)
+
      '''int[n]''' to  <font color=green> // j работа обрабатывается на to[j] станке </font>
      <tex>t1 \leftarrow min(s>t |</tex>находим следующую выполненную работу,где <tex> s</tex> - время ее окончания <tex> ) </tex>
+
      fill(to, -1)
      <tex>t2 \leftarrow </tex> найти минимальное <tex>s > t</tex>. Для которого выполняется для некоторых работ <tex>i</tex> , <tex>j</tex>:<tex> level_i(t)>level_j(t)</tex> и <tex>  level_i(s) == level_j(s)</tex>
+
      '''set<int>''' s  <font color=green> // множество уже распределенных работ </font>
      <tex> t \leftarrow min(t1,t2) </tex> //поиск следующего момента времени ,в который нужно будет перераспределить машины/работы
+
      '''int''' i = 0
  Построение расписания
+
      '''while''' i < m '''and''' i < k
 +
        Находим первый j такой что p[j] максимальный и s не содержит j
 +
        s.add(j)
 +
        m[j] = i++
 +
      '''return''' to
  
Функция <tex>Assign(t)</tex>:
+
===Асимптотика===
 +
<tex>\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>J </tex> - множество работ с положительным <tex>level</tex>
 
  <tex>M = \{M_1,...,M_m\}</tex> - множество всех станков
 
  '''WHILE''' множества <tex>J</tex> и <tex>M</tex> не пустые
 
      Найти множество работ <tex>I</tex> подмножество <tex>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>:
+
{{Теорема
 +
|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 +
|proof=Так как нижняя граница <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>C_{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>
  
 
то достаточно показать, что составленное расписание достигает этой оценки.
 
то достаточно показать, что составленное расписание достигает этой оценки.
  
Будем считать, что в начале алгоритма все работы упорядочены, как было сказано ранее: <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> p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_n(0) </tex>. Это утверждение не меняется на протяжении всего выполнения алгоритма, для любого момента времени. Получаем: <tex> p_1(t) \geqslant p_2(t) \geqslant \ldots \geqslant 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>  T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n </tex> или <tex> T = \dfrac{P_n}{S_m} </tex>
  
 
Таким образом необходимая оценка достигается нашим алгоритмом.
 
Таким образом необходимая оценка достигается нашим алгоритмом.
  
Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, мы имеем следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 ... M_m</tex>:
+
Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как <tex> f_i </tex>) на станках <tex>M_1 \ldots M_m</tex>, пронумерованных по убыванию скоростей:
 +
 
 +
<tex> f_1 \geqslant f_2 \geqslant \ldots \geqslant f_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> 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_{i+1} </tex>. Пришли к противоречию, так как при распределении, работы с наибольшим <tex>\mathrm{level}</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> 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>.
+
Пусть <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 = \dfrac{P_j}{S_j} </tex>.
 +
}}
  
==Пример==
+
===Пример===
 
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]
 
[[Файл:Qpmtncmax.png|600px|thumb|right|Картинка к примеру]]
  
Пусть у нас есть 6 работ и 3 станка. Покажем работу алгоритма для данного случая.
+
Пусть у нас есть <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>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> и все работы закончатся одновременно.
+
==См. также==
 +
* [[QpmtnSumCi|<tex>Q \mid pmtn \mid \sum C_i</tex>]]
  
==Время работы==
+
==Источники информации==
Level-алгоритм вызывает функцию Assign(t) в самом худшем случае <tex>O(n)</tex> раз. Функция Assign(t) выполняется за <tex>O(nm)</tex>. Итоговое время работы <tex>O(n^2m)</tex>.
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 124 {{---}} 129 стр. {{---}} ISBN 978-3-540-69515-8
  
==Литература==
+
[[Категория: Алгоритмы и структуры данных]]
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 379 стр. {{---}} ISBN 978-3-540-69515-8
+
[[Категория: Теория расписаний]]

Версия 02:35, 8 июня 2016

[math]Q \mid pmtn \mid C_{max}[/math]

Задача:
Дано [math]m[/math] станков с разной скоростью выполнения работ, работающих параллельно, и [math]n[/math] работ. Работа может быть прервана в любой момент и продолжена позже на любой машине. Необходимо минимизировать время выполнения всех работ.


Алгоритм построения расписания

Описание алгоритма

Перед выполнением алгоритма, упорядочим все работы по убыванию их времени выполнения:[math] p_1 \geqslant p_2 \geqslant p_3 \ldots \geqslant p_n[/math], а все машины в порядке убывания скоростей: [math] s_1 \geqslant s_2 \geqslant s_3 \ldots \geqslant s_m[/math]. Введем следующие обозначения:

  • [math]P_i = p_1 + \ldots + p_i[/math], [math]i = 1 \ldots n[/math] — сумма первых [math]i[/math] работ
  • [math]S_j = s_1 + \ldots + s_j[/math], [math]j = 1 \ldots m[/math] — сумма скоростей первых [math]j[/math] станков

Необходимое условие для выполнения всех работ в интервале [math][0 \ldots T][/math]:

[math] P_n = p_1 + \ldots + p_n \leqslant s_1T + \ldots + s_mT = S_mT[/math] или [math]\dfrac{P_n}{S_m} \leqslant T[/math]

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

[math]C_{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. [/math]

Перейдем к описанию алгоритма. Будем назвать [math]\mathrm{level}[/math]-ом работы [math] p_i(t) [/math] невыполненную часть работы [math] p_i [/math] в момент времени [math] t [/math].

Далее построим расписание, которое достигает нашей оценки [math]C_{max}[/math], с помощью [math]\mathrm{level}[/math]-алгоритма.

Псевдокод

Функция [math]\mathrm{level}[/math] принимает на вход два массива — массив с объемами работ и массив скоростей обработки станков, и возвращает вектор четвёрок, где первый элемент является номером станка, второй — номером работы, а два оставшихся время начала и окончания обработки этой работы на этом станке.

  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   // количество еще не выполненных работ 
     sort(p)   // сортируем время обработки работ по убыванию 
     sort(s)   // сортируем станки по убыванию скоростей 
     while k > 0
        int[] to = assign(p, k, m)   // получаем распределение работ по станкам 
        Найдем минимальное 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)   // то есть такое минимальное время, через которое, 
                                                                                                         // оставшийся объем каких-нибудь двух работ сравняется 
        int dt = min(dt1, dt2)
        for j = 0 to n - 1
           if p[j] > 0
              if to[j] [math] \neq [/math] -1   // рассматриваем работы которые обрабатываются в данном распределении
                 ans.push(to[j], j, t, t + dt)
                 p[j] -= s[to[i]] * dt
                 if p[j] == 0
                    k--
        t += dt   // поиск следующего момента времени, в который нужно будет перераспределить машины/работы 
     return ans

Функция [math]\mathrm{assign}[/math] принимает на вход массив с объемами работ и возвращает массив с распределением работ.

  function assign(p : int[n], k : int, m : int) : int[]
     int[n] to   // j работа обрабатывается на to[j] станке 
     fill(to, -1)
     set<int> s   // множество уже распределенных работ 
     int i = 0
     while i < m and i < k
        Находим первый j такой что p[j] максимальный и s не содержит j
        s.add(j)
        m[j] = i++
     return to

Асимптотика

[math]\mathrm{level}[/math]-алгоритм вызывает функцию [math]\mathrm{assign}(t) [/math] в самом худшем случае [math]O(n)[/math] раз. Функция [math]\mathrm{assign}(t) [/math] выполняется за [math]O(nm)[/math]. Итоговое время работы [math]O(n^2m)[/math].


Доказательство корректности алгоритма

Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]

Так как нижняя граница [math]C_{max}[/math]:

[math]C_{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. [/math]

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

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

[math] T(s_1 + \ldots + s_m) = p_1 + p_2 + \ldots + p_n [/math] или [math] T = \dfrac{P_n}{S_m} [/math]

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

Допустим хотя бы одна машина простаивает, в момент когда есть невыполненные работы, получим следующее неравенство для времен окончания работ (обозначим далее как [math] f_i [/math]) на станках [math]M_1 \ldots M_m[/math], пронумерованных по убыванию скоростей:

[math] f_1 \geqslant f_2 \geqslant \ldots \geqslant f_m [/math]

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

Предположим, что [math] f_i \lt f_{i+1} [/math] для некоторого [math] 1 \leqslant i \leqslant m-1 [/math]. Тогда [math]\mathrm{level}[/math] последней работы, выполнявшейся на станке [math] M_i [/math] в момент времени [math] f_i - \varepsilon [/math] (где [math] \varepsilon \gt 0[/math] достаточно мал) меньше, чем [math]\mathrm{level}[/math] последней работы на станке [math] M_{i+1} [/math]. Пришли к противоречию, так как при распределении, работы с наибольшим [math]\mathrm{level}[/math] выставлялись на самые быстрые станки.

Пусть [math] T [/math] = [math] f_1 = f_2 = f_3 = \ldots = f_j \gt f_{j+1}[/math] ,где [math] j \lt m [/math]. Чтобы работы завершились в момент времени [math] T [/math], необходимо начать их в момент времени 0, поскольку если это не выполняется, то у нас найдется работа [math] J_i [/math] , которая начинается позже [math] t = 0 [/math] и заканчивается в [math] T [/math]. Это означает, что в момент времени [math] 0 [/math] начинаются как минимум [math] m [/math] работ. Пусть первые [math] m [/math] работ стартовали вместе на всех машинах. Мы получаем [math] p_1(0) \geqslant p_2(0) \geqslant \ldots \geqslant p_m(0) \geqslant p_i(0) [/math], из чего следует, что [math] p_1(T - \varepsilon) \geqslant \ldots \geqslant p_m(T - \varepsilon) \geqslant p_i(T - \varepsilon) \gt 0 [/math] для любого [math] \varepsilon [/math], удовлетворяющего условию [math] 0 \leqslant \varepsilon \lt T - t [/math]. Таким образом, до момента времени [math] T [/math] нет простаивающих машин. Пришли к противоречию. Получаем [math] T = \dfrac{P_j}{S_j} [/math].
[math]\triangleleft[/math]

Пример

Картинка к примеру

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

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

См. также

Источники информации

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 124 — 129 стр. — ISBN 978-3-540-69515-8