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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство корректности алгоритма)
Строка 35: Строка 35:
 
|proof=
 
|proof=
 
Рассмотрим два случая:
 
Рассмотрим два случая:
*<tex>T_{1}(I_{12}) + T_{1}(I_{1}) \geqslant T_{2}(I_{21}) </tex>. Тогда <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}) \geqslant T_{2}(I_{21}) </tex>. Тогда <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>. Тогда <tex>M_{2}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{2}</tex> на <tex> M_{2} </tex> все работы <tex>I_{12}</tex> выполнены на <tex>M_{1}</tex> .  
+
#<tex>T_{1}(I_{12}) + T_{1}(I_{1}) < T_{2}(I_{21}) </tex>. Тогда <tex>M_{2}</tex> работает без прерываний, т.к к моменту завершения выполнения <tex>I_{2}</tex> на <tex> M_{2} </tex> все работы <tex>I_{12}</tex> выполнены на <tex>M_{1}</tex> .  
  
  
Строка 62: Строка 62:
  
 
}}
 
}}
 +
 
==Сложность алгоритма==
 
==Сложность алгоритма==
 
Время работы алгоритма равно времени работы алгоритма  [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]], то есть <tex>O(n\log n)</tex>.
 
Время работы алгоритма равно времени работы алгоритма  [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]], то есть <tex>O(n\log n)</tex>.

Версия 18:23, 17 мая 2016

[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