Изменения

<tex dpi =200>O2 \mid \mid C_{max}</tex>{{Задача|definition= Постановка задачи ==Рассмотрим задачу:<ol><li>*Дано <tex>n</tex> работ и <tex>2</tex> станка.</li><li>*Для каждой работы известно её время выполнения на каждом станке.</li></ol>Требуется минимизировать время окончания всех работ, если каждую работу необходимо выполнить на обоих станках.}}

<ol><li>#Разобьём все работы на два множества: <tex>I = \{i \mid a_{i} \le leqslant b_{i}; i = 1, \dots, n\}</tex> и <tex>J = \{i \mid a_{i} > b_{i}; i = 1, \dots, n\}</tex></li>.<li>#Найдем такие <tex> x </tex> и <tex> y </tex>, что <tex>a_{x} = \max \{a_{i} \mid i \in I\}</tex> и <tex>b_{y} = \max \{b_{i} \mid i \in J\}</tex> </li>.<li>#Построим оптимальное значение целевой функции: <tex>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}\}\}</tex>.</li><li> # Рассмотрим два случая. Первый случай, когда <tex>a_{x} > b_{y}</tex> (он показан на рисунке ниже). Будем строить расписание с двух концов:<ul><li>#*Строим расписание слева: выполняем на первом станке все работы из <tex>I \setminus \{x\}</tex>, а на втором выполняем первой работу <tex>x</tex>, затем <tex>I \setminus \{x\}</tex>.</li><li>#*Теперь, упираясь в правую границу, равную <tex> C_{max} </tex>, можно построить расписание справа: выполняем на первом станке все работы из <tex>J</tex>, затем <tex>x</tex>, а для второго выполняем работы из <tex>J</tex></li></ul>.:Второй случай сводится к первому: все работы и станки меняются местами, и решается задача для первого случая.</li></ol>

Первое утверждение вытекает из того, что мы строили расписание, опираясь на <tex>C_{max}</tex>. Из построения <tex>C_{max} \ge geqslant \sum \limits_{i = 1}^{n}a_{i}, \sum \limits_{i = 1}^{n}b_{i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/>

<ol><li># Для блока <tex> \{x\}</tex> это следует из того, что <tex> C_{max} \ge geqslant a_{x}+b_{x}</tex>, а работа <tex> x </tex> выполняется с разных концов станков. Получили, что отрезки выполнения работы <tex> x </tex> на разных станках не пересекаются.</li><li># Покажем, что любая работа из <tex> I \setminus \{x\}</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits_{i = 1}^k a_{i} \le leqslant \sum \limits_{i = 1}^k b_{i} = \sum \limits_{i = 1}^{k - 1} b_{i} + b_{x}</tex></ul>,где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br/>Это неравенство следует из выбора <tex>I</tex> и из того, что <tex>b_{x} \ge geqslant a_{x} \ge geqslant a_{i}, \forall i \in I</tex>.<br/>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</libr><li># Покажем, что любая работа из <tex>J</tex> начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits_{i = 1}^k b_{i} \le leqslant \sum \limits_{i = 1}^k a_{i} \le leqslant \sum \limits_{i = 1}^{k - 1} a_{i} + a_{x}</tex></ul>,где <tex>1 \dots k</tex> {{---}} это работы, выполняемые на втором станке во время данного блока.<br/>Это неравенство следует из выбора <tex>J</tex> и из того, что <tex>a_{x} \ge geqslant a_{i}, \forall i \in I</tex>.<br/>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.</li></ol>

if <tex>a_{i} \le leqslant b{i}</tex>