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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Описание алгоритма)
м (Доказательство корректности алгоритма)
Строка 28: Строка 28:
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
|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} \ge \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>
Докажем теперь второе утверждение. У нас имеется 3 блока: <tex> I \setminus \{x\}, \{x\}, J</tex>.
+
Докажем теперь второе утверждение. У нас имеется 3 блока работ: <tex> I \setminus \{x\}, \{x\}, J</tex>.
 
<ol>
 
<ol>
<li>Для блока <tex> \{x\}</tex> пересечения отсутствуют из того, что <tex> C_{max} \ge a_{x}+b_{x}</tex>, а этот блок выполняется с разных концов станков, значит он не может пересекаться.</li>
+
<li>Для блока <tex> \{x\}</tex> пересечения отсутствуют из того, что <tex> C_{max} \ge a_{x}+b_{x}</tex>, а этот блок выполняется с разных концов станков, выполнения работы <tex> x </tex> на разных станках не пересекаются.</li>
<li>Для блока <tex> I \setminus \{x\}</tex> рассмотри сумму:
+
<li>Для блока <tex> I \setminus \{x\}</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>
 
<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>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>
 
Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge a_{x} \ge a_{i}, \forall i \in I</tex>.<br/>

Версия 13:58, 21 июня 2012

Постановка задачи

Рассмотрим задачу:

  1. Дано [math]n[/math] работ и [math]2[/math] станка.
  2. Для каждой работы известно её время выполнения на каждом станке.

Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.

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

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

  1. Разобьём все работы на два множества: [math]I = \{i \mid a_{i} \le 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 \{a_{i} \mid i \in I\}[/math] и [math]b_{y} = \max \{b_{i} \mid i \in J\}[/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. Рассмотрим два случая. Первый случай, когда [math]a_{x} \le 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]

    Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая.

O2Cmax.gif

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

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

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

  1. Для блока [math] \{x\}[/math] пересечения отсутствуют из того, что [math] C_{max} \ge a_{x}+b_{x}[/math], а этот блок выполняется с разных концов станков, выполнения работы [math] x [/math] на разных станках не пересекаются.
  2. Для блока [math] I \setminus \{x\}[/math] рассмотрим сумму:
      [math]\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}[/math]

    Это неравенство следует из выбора [math]I[/math] и из того, что [math]b_{x} \ge a_{x} \ge a_{i}, \forall i \in I[/math].

    Получили, что этот блок тоже не пересекается.
  3. Для блока [math]J[/math] рассмотри сумму:
      [math]\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}[/math]

    Это неравенство следует из выбора [math]J[/math] и из того, что [math]a_{x} \ge 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]

Псевдокод

  [math]I \leftarrow \varnothing [/math]
  [math]J \leftarrow \varnothing [/math]
  for [math]i = 1 \dots n[/math]
     if [math]a_{i} \le b{i}[/math]
        [math] I \leftarrow I \cup \{i\} [/math]
     else
        [math] J \leftarrow 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]I, J, x[/math]
     Запомнить, что поменяли
  
  [math]time1 \leftarrow 0[/math]
  shed2[x] [math]\leftarrow 0[/math]
  [math]time2 \leftarrow b_{x}[/math]
  
  Для всех [math]i \in I \setminus \{x\}[/math]
     sched1[i] [math]\leftarrow time1[/math]
     [math]time1 \leftarrow time1 + a_{i}[/math]
     sched2[i] [math]\leftarrow time2[/math]
     [math]time2 \leftarrow time2 + b_{i}[/math]
  
  Для всех [math]i \in J[/math]
     sched1[i] [math]\leftarrow time1[/math]
     [math]time1 \leftarrow time1 + a_{i}[/math]
     sched2[i] [math]\leftarrow time2[/math]
     [math]time2 \leftarrow time2 + b_{i}[/math]
  
  sched1[x] [math]\leftarrow time1[/math]
  [math]time1 \leftarrow time1 + a_{x}[/math]
  
  [math]C_{max} \leftarrow \max\{time1, time2\}[/math]
  if станки меняли местами
     поменять их обратно

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

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