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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Описание алгоритма)
Строка 18: Строка 18:
 
<li><tex>I21</tex> - множество всех работ, которые должны выполнится сначала на <tex>M2</tex> затем на <tex>M1</tex>. </li>
 
<li><tex>I21</tex> - множество всех работ, которые должны выполнится сначала на <tex>M2</tex> затем на <tex>M1</tex>. </li>
 
<ul>
 
<ul>
Режим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I12</tex> и для <tex>I21</tex>. Получим расписание <tex>S12</tex> и <tex>S21</tex>.
+
Реiим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I12</tex> и для <tex>I21</tex>. Получим расписание <tex>S12</tex> и <tex>S21</tex>.
 
Тогда оптимальное расписание для нашей задачи будет следующим:
 
Тогда оптимальное расписание для нашей задачи будет следующим:
 
<ol>
 
<ol>
<li>Расписание <tex>M1</tex>: <tex>I12</tex> в соответсвии с расписанием <tex>S12</tex>. <tex>I1</tex> в произвольном порядке. Затем <tex>I21</tex> в соответсвии с <tex>S21</tex>.
+
<li>Расписание <tex>M1</tex>: <tex>I12</tex> в соответсвии с расписанием <tex>S12</tex>. <tex>I1</tex> в произвольном порядке. Затем <tex>I21</tex> в соответсвии с <tex>S21</tex>. </li>
<li>Расписание <tex>M2</tex>:<tex>I21</tex> в соответсвии с расписанием <tex>S21</tex>. Затем <tex>I2</tex> в произвольном порядке. Затем <tex>I12</tex> в соответсвии с <tex>S12</tex>.
+
<li>Расписание <tex>M2</tex>:<tex>I21</tex> в соответсвии с расписанием <tex>S21</tex>. Затем <tex>I2</tex> в произвольном порядке. Затем <tex>I12</tex> в соответсвии с <tex>S12</tex>. </li>
 
<ul>
 
<ul>
  

Версия 14:34, 22 июня 2013

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

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

  1. Дано [math]n[/math] работ и [math]2[/math] станка.
  2. Для каждой работы известно её время выполнения на каждом станке.
  3. Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. [math]1[/math].
  4. Длина любой последовательности [math]\lt =2[/math].

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

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

[math]M1[/math] - первый станок. [math]M2[/math] - второй станок. Разобьем все работы на четыре множества:

  1. [math]I1[/math] - множество всех работ, которые должны выполнится только на [math]M1[/math].
  2. [math]I2[/math] - множество всех работ, которые должны выполнится только на [math]M2[/math].
  3. [math]I12[/math] - множество всех работ, которые должны выполнится сначала на [math]M1[/math] затем на [math]M2[/math].
  4. [math]I21[/math] - множество всех работ, которые должны выполнится сначала на [math]M2[/math] затем на [math]M1[/math].
    • Реiим задачу [math]F2 \mid \mid C_{max}[/math] для [math]I12[/math] и для [math]I21[/math]. Получим расписание [math]S12[/math] и [math]S21[/math]. Тогда оптимальное расписание для нашей задачи будет следующим:
      1. Расписание [math]M1[/math]: [math]I12[/math] в соответсвии с расписанием [math]S12[/math]. [math]I1[/math] в произвольном порядке. Затем [math]I21[/math] в соответсвии с [math]S21[/math].
      2. Расписание [math]M2[/math]:[math]I21[/math] в соответсвии с расписанием [math]S21[/math]. Затем [math]I2[/math] в произвольном порядке. Затем [math]I12[/math] в соответсвии с [math]S12[/math].
        • Доказательство корректности алгоритма

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

          Доказательство будем вести от противного.
          Рассмотрим расписание [math]S_{1}[/math], полученное после выполнения нашего алгоритма, и оптимальное расписание [math]S_{2}[/math].
          Возьмём первый момент времени [math]t_{1}[/math], когда расписания различаются. Пусть в этот момент времени в [math]S_{1}[/math], будет выполняться работа с весом [math]w_{1}[/math], а в [math]S_{2}[/math] — работа с весом [math]w_{2}[/math].
          Это первый момент, в котором расписания отличаются, значит в [math]S_{2}[/math] работа с весом [math]w_{1}[/math] выполнится в момент времени [math]t_{2} \gt t_{1}[/math].
          Поменяем местами работы с весами [math]w_{1}[/math] и [math]w_{2}[/math] в [math]S_{2}[/math] и полуим расписание [math]S_{3}[/math]. Это возможно, потому что время появления этих работ не меньше [math]t_{1}[/math].
          При такой перестановке ответы на задачу для [math]S_{2}[/math] и [math]S_{3}[/math] будут отличаться на

            [math]t_{1}w_{2} + t_{2}w_{1} - t_{1}w_{1} + t_{2}w_{2} = t_{1}(w_{2} - w_{1}) + t_{2}(w_{1} - w_{2}) = (t_{1} - t_{2})(w_{2} - w_{1})[/math]

          Первая скобка отрицательная: [math]t_{1} \lt t_{2}[/math]. Вторая скобка тоже отрицательная из того, что в [math]S_{1}[/math] работа с весом [math]w_1[/math] выполняется раньше, значит её вес должен быть больше [math]w_2[/math].

          Итого имеем, что ответ для [math]S_{2}[/math] больше, чем ответ для [math]S_{3}[/math]. Следовательно расписание [math]S_2[/math] неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание [math]S_{1}[/math] отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
          [math]\triangleleft[/math]

          Псевдокод

            [math] S \leftarrow \{1 \dots n\}[/math]
            [math] time \leftarrow 0[/math]
            [math] answer \leftarrow 0[/math]
            while [math] S \neq \varnothing [/math]
               [math] j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})[/math]
               if [math]j \neq null [/math]
                  [math] S \leftarrow S \setminus j[/math]
                  [math] Answer \leftarrow Answer + time \cdot w_{j}[/math]
               [math] time++[/math]
          

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

          Время работы алгоритма равно времени работы алгоритма [math]F2 \mid \mid C_{max}[/math].

          Сложность алгоритма [math]O(n\log n)[/math].