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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство корректности алгоритма)
(не показана 21 промежуточная версия 4 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
<tex dpi = 200>O2 \mid \mid C_{max}</tex>
Рассмотрим задачу:
+
{{Задача
<ol>
+
|definition=Рассмотрим задачу:
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
+
*дано <tex>n</tex> работ и <tex>2</tex> станка,
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
+
*для каждой работы известно её время выполнения на каждом станке.
</ol>
+
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.}}
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.
 
  
 
== Описание алгоритма ==
 
== Описание алгоритма ==
 
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
 
Пусть <tex>a_{i}</tex> {{---}} время выполнения <tex>i</tex>-ой работы на первом станке, а <tex>b_{i}</tex> {{---}} на втором.<br/>
<ol>
+
#Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \leqslant b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex>.
<li>Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex></li>
+
#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> и <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>.
<li>Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = \max \{b_{i} \mid i \in J\}</tex> </li>
+
#Построим оптимальное значение целевой функции: <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>.
<li>Построим оптимальное значение целевой функции: <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \sum \limits_{i = 1}^{n} b_i, \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>.</li>
+
# Рассмотрим два случая:
<li> Рассмотрим два случая. Первый случай, когда <tex>a_{x} \le b_{y}</tex>. Будем строить расписание с двух концов:
+
## <tex>a_{x} > b_{y}</tex>. Будем строить расписание с двух концов:
<ul>
+
##*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex> в том же порядке, что и на первом станке.
<li>Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.</li>
+
##*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex>.[[Файл:Picture2.gif‎|500px|center]]
<li>Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex></li>
+
## <tex>a_{x} \leqslant b_{y}</tex>. Сводится к первому, если поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.
</ul>
 
Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая.
 
</li>
 
</ol>
 
[[Файл:O2Cmax.gif|300px|center]]
 
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 29: Строка 23:
 
|proof=
 
|proof=
 
Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.<br/>
 
Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.<br/>
Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \ge \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>
+
Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>
Докажем теперь второе утверждение. У нас имеется 3 блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
+
Докажем теперь второе утверждение. У нас имеется три блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
<ol>
+
# Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \geqslant a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.
<li>Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \ge a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.</li>
+
# Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex>, где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I</tex>.<br>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.<br>
<li>Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
+
# Покажем, что любая работа из <tex>J</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<br><tex>\sum \limits_{i = 1}^k b_{i} \leqslant \sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex>, где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на втором станке во время данного блока.
<ul><tex>\sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex></ul>
+
Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \geqslant a_{i}, \forall i \in I</tex>.
Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
+
Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.
Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается .</li>
+
 
<li>Для блока <tex>J</tex> рассмотрим сумму:
 
<ul><tex>\sum \limits_{i = 1}^k b_{i} \le \sum \limits_{i = 1}^k a_{i} \le \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex></ul>
 
Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
 
Получили, что этот блок тоже не пересекается.</li>
 
</ol>
 
 
Итого мы доказали корректность.<br/>
 
Итого мы доказали корректность.<br/>
Оптимальность вытекает из того, что <tex>C_{max}</tex> не может быть меньше <tex>\sum \limits_{i = 1}^{n} a_i, \sum \limits_{i = 1}^{n} b_i, \max \limits_{i = 1}^{n}\{a_i + b_{i}\}</tex>, а из построения оно равно максимуму из этих значений.
+
Оптимальность вытекает из того, что <tex>C_{max}</tex> не может быть меньше <tex>\sum \limits_{i = 1}^{n} a_i,\ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}</tex>, а из построения оно равно максимуму из этих значений.
 
}}
 
}}
  
 
==Псевдокод==
 
==Псевдокод==
  <tex>I \leftarrow \varnothing </tex>
+
<font color=green>//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.<br>//Функция возвращает пару из расписания для первого станка и расписания для второго станка.</font>
  <tex>J \leftarrow \varnothing </tex>
+
'''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>'''
  for <tex>i = 1 \dots n</tex>
+
    <tex>I = \varnothing </tex>
      if <tex>a_{i} \le b{i}</tex>
+
    <tex>J = \varnothing </tex>
        <tex> I \leftarrow I \cup \{i\} </tex>
+
    <tex>C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \  \sum \limits_{i = 1}^{n} b_i, \  \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}</tex>
      else
+
    '''for''' <tex>i = 1</tex> '''to''' <tex>n</tex>
        <tex> J \leftarrow J \cup \{i\} </tex>
+
        '''if''' <tex>a_{i} \leqslant b_{i}</tex>
  Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
+
          <tex> I = I \cup \{i\} </tex>
  Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
+
        '''else'''
  if <tex>a_{x} > b_{y}</tex>
+
          <tex> J = J \cup \{i\} </tex>
      Поменять местами первый и второй станок
+
    Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex>
      Пересчитать <tex>I, J, x</tex>
+
    Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex>
      Запомнить, что поменяли
+
    '''if''' <tex>a_{x} > b_{y}</tex>
 
+
        Начиная с <tex>0</tex> на первом станке расставляем расписание для <tex>I \setminus \{x\}</tex>
  <tex>time1 \leftarrow 0</tex>
+
        Начиная с <tex>0</tex> на втором станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>I \setminus \{x\}</tex><br/>
  shed2[x] <tex>\leftarrow 0</tex>
+
        От правой границы {{---}} <tex>C_{max}</tex> на первом станке расставляем расписание для <tex>\{x\}</tex>, затем для <tex>J</tex>
  <tex>time2 \leftarrow b_{x}</tex>
+
        От правой границы {{---}} <tex>C_{max}</tex> на втором станке расставляем расписание для <tex>J</tex><br/>
 
+
        '''pair<int[n], int[n]>''' ans = пара из расписания для первого станка и расписания для второго станка
  Для всех <tex>i \in I \setminus \{x\}</tex>
+
        '''return''' ans
      sched1[i] <tex>\leftarrow time1</tex>
+
    '''else'''
      <tex>time1 \leftarrow time1 + a_{i}</tex>
+
        '''pair<int[n], int[n]>''' ans = scheduling(b, a)
      sched2[i] <tex>\leftarrow time2</tex>
+
        Меняем местами расписания для станков в ans
      <tex>time2 \leftarrow time2 + b_{i}</tex>
+
        '''return''' ans
 
 
  Для всех <tex>i \in J</tex>
 
      sched1[i] <tex>\leftarrow time1</tex>
 
      <tex>time1 \leftarrow time1 + a_{i}</tex>
 
      sched2[i] <tex>\leftarrow time2</tex>
 
      <tex>time2 \leftarrow time2 + b_{i}</tex>
 
 
 
  sched1[x] <tex>\leftarrow time1</tex>
 
  <tex>time1 \leftarrow time1 + a_{x}</tex>
 
 
 
  <tex>C_{max} \leftarrow \max\{time1, time2\}</tex>
 
  if станки меняли местами
 
      поменять их обратно
 
  
 
==Сложность алгоритма==
 
==Сложность алгоритма==
 
Каждое из множеств в сумме содержит <tex>n</tex> элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется <tex>O(n)</tex> операций, чтобы составить расписание для каждой работы из множества нам потребуется так же <tex>O(n)</tex> операций. Получаем сложность алгоритма <tex>O(n)</tex>.
 
Каждое из множеств в сумме содержит <tex>n</tex> элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется <tex>O(n)</tex> операций, чтобы составить расписание для каждой работы из множества нам потребуется так же <tex>O(n)</tex> операций. Получаем сложность алгоритма <tex>O(n)</tex>.
 +
 +
==См. также==
 +
* [[P2precpi1Lmax|<tex>P2 \mid prec, p_i = 1 \mid L_{\max}</tex>]]
 +
* [[R2Cmax|<tex>R2 \mid \mid C_{max}</tex>]]
 +
* [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]]
 +
* [[O2Cmax|<tex>O2 \mid \mid C_{max}</tex>]]
 +
* [[J2ni2Cmax|<tex>J2 \mid n_{i} \leqslant 2 \mid C_{max}</tex>]]
 +
* [[J2pij1Lmax| <tex>J2\mid p_{ij} = 1\mid L_{max}</tex>]]
 +
 +
== Источники информации ==
 +
* Peter Brucker «Scheduling Algorithms», fifth edition, Springer {{---}} с. 158{{---}}160 ISBN 978-3-540-69515-8
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Теория расписаний]]

Версия 20:43, 18 мая 2016

[math]O2 \mid \mid C_{max}[/math]

Задача:
Рассмотрим задачу:
  • дано [math]n[/math] работ и [math]2[/math] станка,
  • для каждой работы известно её время выполнения на каждом станке.
Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.


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

Пусть [math]a_{i}[/math] — время выполнения [math]i[/math]-ой работы на первом станке, а [math]b_{i}[/math] — на втором.

  1. Разобьём все работы на два множества: [math]I = \{i \mid a_{i} \leqslant b_{i}; i = 1, \dots, n\}[/math] и [math]J = \{i \mid a_{i} \gt b_{i}; i = 1, \dots, n\}[/math].
  2. Найдем такие [math] x [/math] и [math] y [/math], что [math]a_{x} = \max \limits_{i \in I} \{a_{i}\}[/math] и [math]b_{y} = \max \limits_{i \in J} \{b_{i}\}[/math].
  3. Построим оптимальное значение целевой функции: [math]C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}[/math].
  4. Рассмотрим два случая:
    1. [math]a_{x} \gt b_{y}[/math]. Будем строить расписание с двух концов:
      • Строим расписание слева: выполняем на первом станке все работы из [math]I \setminus \{x\}[/math], а на втором выполняем первой работу [math]x[/math], затем [math]I \setminus \{x\}[/math] в том же порядке, что и на первом станке.
      • Теперь, упираясь в правую границу, равную [math] C_{max} [/math], можно построить расписание справа: выполняем на первом станке все работы из [math]J[/math], затем [math]x[/math], а для второго выполняем работы из [math]J[/math].
        Picture2.gif
    2. [math]a_{x} \leqslant b_{y}[/math]. Сводится к первому, если поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.

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

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

Чтобы доказать корректность, надо доказать, что на каждом станке в любой момент времени выполняется не более одной работы, и что каждая работа в каждый момент времени выполняется не более, чем на одном станке.
Первое утверждение вытекает из того, что мы строили расписание, опираясь на [math]C_{max}[/math]. Из построения [math]C_{max} \geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}[/math], следовательно на каждом станке в любой момент времени выполняется не более одной работы.
Докажем теперь второе утверждение. У нас имеется три блока работ: [math] I \setminus \{x\}, \{x\}, J[/math].

  1. Для блока [math] \{x\}[/math] это следует из того, что [math] C_{max} \geqslant a_{x}+b_{x}[/math], а работа [math] x [/math] выполняется с разных концов станков. Получили, что отрезки выполнения работы [math] x [/math] на разных станках не пересекаются.
  2. Покажем, что любая работа из [math] I \setminus \{x\}[/math] начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
    [math]\sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}[/math], где [math]1 \dots k[/math] — это работы, выполняемые на первом станке во время данного блока.
    Это неравенство следует из выбора [math]I[/math] и из того, что [math]b_{x} \geqslant a_{x} \geqslant a_{i}, \forall i \in I[/math].
    Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.
  3. Покажем, что любая работа из [math]J[/math] начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:
    [math]\sum \limits_{i = 1}^k b_{i} \leqslant \sum \limits_{i = 1}^k a_{i} \leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}[/math], где [math]1 \dots k[/math] — это работы, выполняемые на втором станке во время данного блока.

Это неравенство следует из выбора [math]J[/math] и из того, что [math]a_{x} \geqslant a_{i}, \forall i \in I[/math]. Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.

Итого мы доказали корректность.

Оптимальность вытекает из того, что [math]C_{max}[/math] не может быть меньше [math]\sum \limits_{i = 1}^{n} a_i,\ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}[/math], а из построения оно равно максимуму из этих значений.
[math]\triangleleft[/math]

Псевдокод

//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.
//Функция возвращает пару из расписания для первого станка и расписания для второго станка.
function scheduling(a: int[n], b: int[n]): pair<int[n], int[n]> [math]I = \varnothing [/math] [math]J = \varnothing [/math] [math]C_{max} = \max \{\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i, \ \max \limits_{i = 1}^{n}\{a_i + b_{i}\}\}[/math] for [math]i = 1[/math] to [math]n[/math] if [math]a_{i} \leqslant b_{i}[/math] [math] I = I \cup \{i\} [/math] else [math] J = J \cup \{i\} [/math] Найти [math]x[/math], где [math]a_{x} = \max \limits_{i \in I} \{a_{i}\}[/math] Найти [math]y[/math], где [math]b_{y} = \max \limits_{i \in J} \{b_{i}\}[/math] if [math]a_{x} \gt b_{y}[/math] Начиная с [math]0[/math] на первом станке расставляем расписание для [math]I \setminus \{x\}[/math] Начиная с [math]0[/math] на втором станке расставляем расписание для [math]\{x\}[/math], затем для [math]I \setminus \{x\}[/math]
От правой границы — [math]C_{max}[/math] на первом станке расставляем расписание для [math]\{x\}[/math], затем для [math]J[/math] От правой границы — [math]C_{max}[/math] на втором станке расставляем расписание для [math]J[/math]
pair<int[n], int[n]> ans = пара из расписания для первого станка и расписания для второго станка return ans else pair<int[n], int[n]> ans = scheduling(b, a) Меняем местами расписания для станков в ans return ans

Сложность алгоритма

Каждое из множеств в сумме содержит [math]n[/math] элементов. Следовательно, чтобы найти максимум в каждом из множеств нам потребуется [math]O(n)[/math] операций, чтобы составить расписание для каждой работы из множества нам потребуется так же [math]O(n)[/math] операций. Получаем сложность алгоритма [math]O(n)[/math].

См. также

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

  • Peter Brucker «Scheduling Algorithms», fifth edition, Springer — с. 158—160 ISBN 978-3-540-69515-8