Изменения

<tex dpi =200>J2 \mid n_i \leqslant 2 \mid C_{max}</tex>{{Задача|definition=Постановка задачи==Рассмотрим задачу:<ol><li>*Дано <tex>n</tex> работ и <tex>2</tex> станка.</li><li>*Для каждой работы известно её время выполнения на каждом станке.<tex>p_{ij}</litex>.<li>*Для каждой работы известна последовательность <tex>O_{i1}, \ O_{i2} \ \ldots \ O_{ik}</tex> станков {{--- }} порядок, в котором нужно выполнить работу. <tex>1</tex>.</li><li>Длина любой *В каждой последовательности <tex><=2O_{i}</tex>не более двух элементов.</ol>Требуется минимизировать время окончания выполнения всех работ.}}

<tex>M_{1}</tex> {{--- }} первый станок. <tex>M_{2}</tex> {{--- }} второй станок.

<ol><li>#<tex>I_{1}</tex> {{- --}} множество всех работ, которые должны выполнится выполниться только на <tex>M_{1}</tex>. </li><li>#<tex>I_{2}</tex> {{- --}} множество всех работ, которые должны выполнится выполниться только на <tex>M_{2}</tex>. </li><li>#<tex>I_{12}</tex> {{- --}} множество всех работ, которые должны выполнится выполниться сначала на <tex>M_{1}</tex> затем на <tex>M_{2}</tex>. </li><li>#<tex>I_{21}</tex> {{--- }} множество всех работ, которые должны выполнится выполниться сначала на <tex>M_{2}</tex> затем на <tex>M_{1}</tex>. </li></ol>Решим задачу [[F2Cmax|<tex>F2 \mid \mid C_{max}</tex>]] для <tex>I_{12}</tex> и для <tex>I_{21}</tex>независимо. Получим расписание <tex>S_{12}</tex> и <tex>S_{21}</tex>.

<ol><li>* Расписание <tex>M1M_{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}</litex>. Затем <tex>I_{2}</tex> в произвольном порядке. Затем <tex>I_{12}</tex> в соответсвии с <tex>S_{12}</tex>.

<li>Расписание <tex>M_{2}</tex> : сначала <tex>I_{21}</tex> в соответсвии с расписанием <tex>S_{21}</tex>. Затем <tex>I_{2}</tex> в произвольном порядке. Затем <tex>I_{12}</tex> в соответсвии с <tex>S_{12}</tex>. </li></ol>'''Примечание''': во время выполнения <tex>I_{21}</tex> на <tex>M_{1}</tex> или <tex>I_{12}</tex> на <tex>M_{2}</tex> могут возникнуть простои

|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> .   

Доказательство будем вести от противного[[Файл: j2ni2cmax.<br/>jpg|400px|thumb|right|Рассмотрим расписание <tex>S_{1}</tex>, полученное после выполнения нашего алгоритма, и оптимальное расписание <tex>S_{2}</tex>Рис.<br/>Возьмём первый момент времени <tex>t_{1}</tex>, когда расписания различаются. Пусть в этот момент времени в <tex>S_{1}</tex>, будет выполняться работа с весом <tex>w_{1}</tex>, а в <tex>S_{2}</tex> {{---}} работа с весом <tex>w_{2}</tex>Расположение работ.<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_M_{1}</tex>работает без прерываний.<br/>При такой перестановке ответы Рассмотрим станок на задачу для котором достигается <tex>S_C_{2max}</tex> и . *Если это <tex>S_M_{31}</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_C_{1max} - w_\geqslant \sum\limits_{2}) = (t_i \in G_{1} - t_{2})(w_{2} - w_p_{1i1})</tex></ul>.Первая скобка отрицательная: *Иначе <tex>t_C_{1} < t_{2max}</tex>. Вторая скобка тоже отрицательная из того, что в достигается на <tex>S_M_{12}</tex> работа с весом <tex>w_1</tex> выполняется раньше, значит её вес должен быть больше <tex>w_2</tex>.<br/>Итого имеем, что ответ для Тогда либо <tex>S_M_{2}</tex> больше, чем ответ для работает без прерываний и оптимальность очевидна.Или есть прерывания.Тогда целевая функция равна ответу задачи [[F2Cmax|<tex>S_F2 \mid \mid C_{3max}</tex>. Следовательно расписание <tex>S_2</tex> неоптимальное. Получили противоречие. Значит не существует такого момента времени, когда расписание ]] для работ <tex>S_I_{121}</tex> отличается от оптимального. Следовательно мы доказали, что оно оптимальноекоторый оптимален. 

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

Сложность алгоритма <tex>O(n\log n)</tex>==Источники информации==* Peter Brucker.«Scheduling Algorithms» {{---}} «Springer», 2006 г. {{---}} 179 {{---}} 180 стр. {{---}} ISBN 978-3-540-69515-8