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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Описание алгоритма)
 
(не показаны 24 промежуточные версии 5 участников)
Строка 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]]
 
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
Строка 28: Строка 22:
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
|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>, а этот блок выполняется с разных концов станков, значит он не может пересекаться.</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