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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 100 промежуточных версий 5 участников)
Строка 1: Строка 1:
−
==Постановка задачи==
+
<tex dpi = 200>J2 \mid n_i \leqslant 2 \mid C_{max}</tex>
−
Рассмотрим задачу:
+
{{Задача
−
<ol>
+
|definition=Рассмотрим задачу:
−
<li>Дано <tex>n</tex> работ и <tex>2</tex> станка.</li>
+
*Дано <tex>n</tex> работ и <tex>2</tex> станка.
−
<li>Для каждой работы известно её время выполнения на каждом станке.</li>
+
*Для каждой работы известно её время выполнения на каждом станке <tex>p_{ij}</tex>.
−
<li>Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. <tex>1</tex>.</li>
+
*Для каждой работы известна последовательность <tex>O_{i1}, \ O_{i2} \ \ldots \ O_{ik}</tex> станков {{---}} порядок, в котором нужно выполнить работу.  
−
<li>Длина любой последовательности <tex><=2</tex>.
+
*В каждой последовательности <tex>O_{i}</tex> не более двух элементов.
−
</ol>
+
Требуется минимизировать время окончания выполнения всех работ. }}
−
Требуется минимизировать время окончания выполнения всех работ.
 
  
 
==Описание алгоритма==
 
==Описание алгоритма==
 +
<tex>M_{1}</tex> {{---}} первый станок. <tex>M_{2}</tex> {{---}} второй станок.
  
 +
Разобьем все работы на четыре множества:
 +
#<tex>I_{1}</tex> {{---}} множество всех работ, которые должны выполниться только на <tex>M_{1}</tex>.
 +
#<tex>I_{2}</tex> {{---}} множество всех работ, которые должны выполниться только на <tex>M_{2}</tex>.
 +
#<tex>I_{12}</tex> {{---}} множество всех работ, которые должны выполниться сначала на <tex>M_{1}</tex> затем на <tex>M_{2}</tex>.
 +
#<tex>I_{21}</tex> {{---}} множество всех работ, которые должны выполниться сначала на <tex>M_{2}</tex> затем на <tex>M_{1}</tex>.
 +
Решим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I_{12}</tex> и для <tex>I_{21}</tex> независимо. Получим расписание <tex>S_{12}</tex> и <tex>S_{21}</tex>.
 +
 +
Тогда оптимальное расписание для нашей задачи будет следующим:
 +
* Расписание <tex>M_{1}</tex>: сначала <tex>I_{12}</tex> в соответсвии с расписанием <tex>S_{12}</tex>. Затем <tex>I_{1}</tex> в произвольном порядке. Затем <tex>I_{21}</tex> в соответсвии с <tex>S_{21}</tex>.
 +
* Расписание <tex>M_{2}</tex>: сначала <tex>I_{21}</tex> в соответсвии с расписанием <tex>S_{21}</tex>. Затем <tex>I_{2}</tex> в произвольном порядке. Затем <tex>I_{12}</tex> в соответсвии с <tex>S_{12}</tex>.
 +
 +
'''Примечание''': во время выполнения <tex>I_{21}</tex> на <tex>M_{1}</tex> или <tex>I_{12}</tex> на <tex>M_{2}</tex> могут возникнуть простои
 +
из-за того, что работа ещё не выполнилась на предыдущем станке.
  
 
==Доказательство корректности алгоритма==
 
==Доказательство корректности алгоритма==
 +
<tex>T_{j}(x)</tex> {{---}} время выполнения множества работ <tex>x</tex> на станке <tex>j</tex>.
 +
 +
<tex>G_{j}</tex> {{---}} множество всех работ, которые нужно сделать хотя бы раз на <tex>j</tex>-м станке, то есть <tex>G_{1} = I_{1} \cup I_{12} \cup I_{21}</tex>.
 +
{{Лемма
 +
|id=lemma1
 +
|statement=
 +
Расписание, построенное данным алгоритмом, обладает следующим свойством: один из станков работает без простоев.
 +
|proof=
 +
Рассмотрим два случая:
 +
#<tex>T_{1}(I_{12}) + T_{1}(I_{1}) \geqslant T_{2}(I_{21}) </tex>.<br>Тогда <tex>M_{1}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{1}</tex> на <tex> M_{1} </tex> все работы <tex>I_{21}</tex> выполнены на <tex>M_{2}</tex>.
 +
#<tex>T_{1}(I_{12}) + T_{1}(I_{1}) < T_{2}(I_{21}) </tex>.<br>Тогда <tex>M_{2}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{2}</tex> на <tex> M_{2} </tex> все работы <tex>I_{12}</tex> выполнены на <tex>M_{1}</tex> .
 +
 +
 +
}}
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
 
|proof=
 
|proof=
−
Доказательство будем вести от противного.<br/>
+
[[Файл: j2ni2cmax.jpg|400px|thumb|right|
−
Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>.<br/>
+
Рис. 1 {{---}} Расположение  работ.
−
Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания  различаются. Пусть в этот момент времени  в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>.<br/>
+
<br>
−
Это первый момент, в котором расписания отличаются, значит в <tex>S_{2}</tex> работа с весом <tex>w_{1}</tex> выполнится в момент времени <tex>t_{2} > t_{1}</tex>.<br/>
+
В серой области могут быть прерывания.
−
Поменяем местами работы с весами <tex>w_{1}</tex> и <tex>w_{2}</tex> в <tex>S_{2}</tex> и полуим расписание <tex>S_{3}</tex>. Это возможно, потому что время появления этих работ не меньше <tex>t_{1}</tex>.<br/>
+
]]
−
При такой перестановке ответы на задачу для <tex>S_{2}</tex> и <tex>S_{3}</tex> будут отличаться на
+
Корректность алгоритма очевидна.
−
<ul><tex>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})</tex></ul>
+
Докажем оптимальность.
−
Первая скобка отрицательная: <tex>t_{1} < t_{2}</tex>. Вторая скобка тоже отрицательная из того, что в <tex>S_{1}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>
+
 
−
Итого имеем, что ответ для <tex>S_{2}</tex> больше, чем ответ для <tex>S_{3}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание <tex>S_{1}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальное.
+
Пусть, для опеределенности <tex>M_{1}</tex> работает без прерываний.
 +
 
 +
Рассмотрим станок на котором достигается <tex>C_{max}</tex> .
 +
*Если это <tex>M_{1}</tex>, то оптимальность очевидна <tex>(C_{max} \geqslant \sum\limits_{i \in G_{1}} p_{i1})</tex>.
 +
*Иначе <tex>C_{max}</tex> достигается на <tex>M_{2}</tex>.
 +
Тогда либо <tex>M_{2}</tex> работает без прерываний и оптимальность очевидна.
 +
Или есть прерывания.
 +
Тогда целевая функция равна ответу задачи [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для работ <tex>I_{21}</tex>, который оптимален.
 +
 
 
}}
 
}}
  
−
==Псевдокод==
+
==Сложность алгоритма==
−
  <tex> S \leftarrow \{1 \dots n\}</tex>
+
Время работы алгоритма равно времени работы алгоритма  [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]], то есть <tex>O(n\log n)</tex>.
−
  <tex> time \leftarrow 0</tex>
 
−
  <tex> answer \leftarrow 0</tex>
 
−
  while <tex> S \neq \varnothing </tex>
 
−
      <tex> j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})</tex>
 
−
      if <tex>j \neq null </tex>
 
−
        <tex> S \leftarrow S \setminus j</tex>
 
−
        <tex> Answer \leftarrow Answer + time \cdot w_{j}</tex>
 
−
      <tex> time++</tex>
 
  
−
==Сложность алгоритма==
+
==Источники информации==
−
Время работы алгоритма равно времени работы алгоритма * [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]].
+
* Peter Brucker. «Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 179 {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8
−
Сложность алгоритма <tex>O(n\log n)</tex>.
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория расписаний]]
 
[[Категория: Теория расписаний]]

Текущая версия на 19:29, 4 сентября 2022

[math]J2 \mid n_i \leqslant 2 \mid C_{max}[/math]

Задача:
Рассмотрим задачу:
  • Дано [math]n[/math] работ и [math]2[/math] станка.
  • Для каждой работы известно её время выполнения на каждом станке [math]p_{ij}[/math].
  • Для каждой работы известна последовательность [math]O_{i1}, \ O_{i2} \ \ldots \ O_{ik}[/math] станков — порядок, в котором нужно выполнить работу.
  • В каждой последовательности [math]O_{i}[/math] не более двух элементов.
Требуется минимизировать время окончания выполнения всех работ.


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

[math]M_{1}[/math] — первый станок. [math]M_{2}[/math] — второй станок.

Разобьем все работы на четыре множества:

  1. [math]I_{1}[/math] — множество всех работ, которые должны выполниться только на [math]M_{1}[/math].
  2. [math]I_{2}[/math] — множество всех работ, которые должны выполниться только на [math]M_{2}[/math].
  3. [math]I_{12}[/math] — множество всех работ, которые должны выполниться сначала на [math]M_{1}[/math] затем на [math]M_{2}[/math].
  4. [math]I_{21}[/math] — множество всех работ, которые должны выполниться сначала на [math]M_{2}[/math] затем на [math]M_{1}[/math].

Решим задачу [math]F2 \mid \mid C_{max}[/math] для [math]I_{12}[/math] и для [math]I_{21}[/math] независимо. Получим расписание [math]S_{12}[/math] и [math]S_{21}[/math].

Тогда оптимальное расписание для нашей задачи будет следующим:

  • Расписание [math]M_{1}[/math]: сначала [math]I_{12}[/math] в соответсвии с расписанием [math]S_{12}[/math]. Затем [math]I_{1}[/math] в произвольном порядке. Затем [math]I_{21}[/math] в соответсвии с [math]S_{21}[/math].
  • Расписание [math]M_{2}[/math]: сначала [math]I_{21}[/math] в соответсвии с расписанием [math]S_{21}[/math]. Затем [math]I_{2}[/math] в произвольном порядке. Затем [math]I_{12}[/math] в соответсвии с [math]S_{12}[/math].

Примечание: во время выполнения [math]I_{21}[/math] на [math]M_{1}[/math] или [math]I_{12}[/math] на [math]M_{2}[/math] могут возникнуть простои из-за того, что работа ещё не выполнилась на предыдущем станке.

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

[math]T_{j}(x)[/math] — время выполнения множества работ [math]x[/math] на станке [math]j[/math].

[math]G_{j}[/math] — множество всех работ, которые нужно сделать хотя бы раз на [math]j[/math]-м станке, то есть [math]G_{1} = I_{1} \cup I_{12} \cup I_{21}[/math].

Лемма:
Расписание, построенное данным алгоритмом, обладает следующим свойством: один из станков работает без простоев.
Доказательство:
[math]\triangleright[/math]

Рассмотрим два случая:

  1. [math]T_{1}(I_{12}) + T_{1}(I_{1}) \geqslant T_{2}(I_{21}) [/math].
    Тогда [math]M_{1}[/math] работает без прерываний, т.к к моменту завершения выполнения [math]I_{1}[/math] на [math] M_{1} [/math] все работы [math]I_{21}[/math] выполнены на [math]M_{2}[/math].
  2. [math]T_{1}(I_{12}) + T_{1}(I_{1}) \lt T_{2}(I_{21}) [/math].
    Тогда [math]M_{2}[/math] работает без прерываний, т.к к моменту завершения выполнения [math]I_{2}[/math] на [math] M_{2} [/math] все работы [math]I_{12}[/math] выполнены на [math]M_{1}[/math] .
[math]\triangleleft[/math]
Теорема:
Расписание, построенное данным алгоритмом, является корректным и оптимальным.
Доказательство:
[math]\triangleright[/math]
Рис. 1 — Расположение работ.
В серой области могут быть прерывания.

Корректность алгоритма очевидна. Докажем оптимальность.

Пусть, для опеределенности [math]M_{1}[/math] работает без прерываний.

Рассмотрим станок на котором достигается [math]C_{max}[/math] .

  • Если это [math]M_{1}[/math], то оптимальность очевидна [math](C_{max} \geqslant \sum\limits_{i \in G_{1}} p_{i1})[/math].
  • Иначе [math]C_{max}[/math] достигается на [math]M_{2}[/math].

Тогда либо [math]M_{2}[/math] работает без прерываний и оптимальность очевидна. Или есть прерывания.

Тогда целевая функция равна ответу задачи [math]F2 \mid \mid C_{max}[/math] для работ [math]I_{21}[/math], который оптимален.
[math]\triangleleft[/math]

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

Время работы алгоритма равно времени работы алгоритма [math]F2 \mid \mid C_{max}[/math], то есть [math]O(n\log n)[/math].

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

  • Peter Brucker. «Scheduling Algorithms» — «Springer», 2006 г. — 179 — 180 стр. — ISBN 978-3-540-69515-8
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=J2ni2Cmax&oldid=85330»