Изменения

<div styletex dpi ="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;"200>Эта статья находится в разработке!O2 \mid \mid C_{max}</div><includeonly>[[Категория: В разработке]]</includeonlytex>{{Задача|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>.#Найдем такие <tex> x </litex> и <tex>y <li/tex>Найдем , что <tex>a_{x} = \max \limits_{i \in I} \{a_{i} \mid }</tex> и <tex>b_{y} = \max \limits_{i \in IJ} \{b_{i}\}</tex> и .#Построим оптимальное значение целевой функции: <tex>b_C_{ymax} = \max \{b_\sum \limits_{i = 1}^{n} a_i, \ \sum \limits_{i = 1}^{n} b_i,\ \max \limits_{i= 1}^{n} \mid {a_i + b_{i }\in J}\}</tex> </li>.<li> # Рассмотрим 2 два случая. Первый случай, когда :## <tex>a_{x} \ge > b_{y}</tex>, тогда. Будем строить расписание с двух концов:<ul><li>Выполняем все работы ##*Строим расписание слева: выполняем на первом станке в следующем порядке: сперва все работы из <tex>I \setminus \{x\}</tex>, затем из <tex>J</tex> и последней а на втором выполняем первой работу <tex>x</tex></li><li>На втором станке выполняем первой работу , затем <tex>I \setminus \{x\}</tex></li><li>Остальные работы выполняем на втором станке в том же порядке их завершения , что и на первом тогдастанке.##*Теперь, когда второй станок свободенупираясь в правую границу, а работа на первом уже выполненаравную </litex>C_{max} </ultex>Второй случай рассматривается аналогично, можно построить расписание справа: первый и второй станок меняются местами, и вместо выполняем на первом станке все работы из <tex>xJ</tex> {{---}} работа , затем <tex>yx</tex>, а для второго выполняем работы из </litex>J</oltex>.[[Файл:O2CmaxPicture2.gifgif‎|300px500px|center]]## <tex>a_{x} \leqslant b_{y}</tex>. Сводится к первому, если поменять местами станки и соответствующие списки времён выполнения, при этом надо заново выполнить пункты 1,2 и 3. При выдаче ответа меняем станки обратно местами.

Для доказательства оптимальности полученного расписания рассмотрим только первый случай. Второй доказывается аналогично{{Теорема|statement=Расписание, построенное данным алгоритмом, является корректным и оптимальным.Рассмотрим 3 последовательности выполнения работы|proof=Чтобы доказать корректность, надо доказать, начиная с нулевого что на каждом станке в любой момент времени: все выполняется не более одной работы на первом станке, все работы на втором станке и первая что каждая работа в каждый момент времени выполняется не более, чем на втором одном станке плюс последняя - на первом.<br/>ДокажемПервое утверждение вытекает из того, что время окончания одной из этих трёх последовательностей максимальное из всех возможных окончаний.мы строили расписание, опираясь на <br/tex>Пронумеруем работы в порядке выполнения их на первом станке и рассмотрим последовательностьC_{max}<br/tex><ul>. Из построения <tex>0 \rightarrow a_C_{1max} \rightarrow geqslant \dots sum \rightarrow limits_{i = 1}^{n}a_{i} , \rightarrow b_sum \limits_{i= 1}^{n} \rightarrow \dots \rightarrow b_{n-1i}</tex>, следовательно на каждом станке в любой момент времени выполняется не более одной работы.<br/ul>Докажем теперь второе утверждение. У нас имеется три блока работ: <oltex>I \setminus \{x\}, \{x\}, J<li/tex>Если .# Для блока <tex>i \in I{x\}</tex>это следует из того, то<ul>что <tex>\sum \limits _{j = 1}^{i}a_{j} + \sum\limits_{j = i}^{n -1}b_C_{jmax} \le \sum\limits_{j = 1}^{i-1}b_{j} +geqslant a_{ix}+ \sum\limits_{j = i}^{n -1}b_{jx}</tex>, а работа <tex> x </ultex>Это неравенство получаем из первого случая и тоговыполняется с разных концов станков. Получили, что отрезки выполнения работы <tex>i \in I \Rightarrow \ \forall j x < i/tex> на разных станках не пересекаются.# Покажем, j \in что любая работа из <tex> I \Rightarrow setminus \forall j < i, a_{j} x\le b_{j}</tex>начинает выполняться на втором станке позже, чем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits_{j i = 1}^{i-1}b_{j} +k a_{i}+ \leqslant \sum\limits_{j i = i1}^{n -1}k b_{ji} \le = \sum \limits_{j i = 1}^{nk - 1} b_{i} + b_{jx}</tex>, где <tex>1 \dots k</ultex> {{---}} это работы, выполняемые на первом станке во время данного блока.<br>Это неравенство получено следует из выбора <tex>I</tex> и из того, что <tex>a_b_{ix} \le geqslant a_{nx} \le b_geqslant a_{ni}</tex>, где <tex>n = x\forall i \in I</tex>.</libr>Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом.<libr>Если # Покажем, что любая работа из <tex>i \in J</tex>начинает выполняться на втором станке позже, точем заканчивает выполняться на первом. Для этого рассмотрим сумму:<ulbr><tex>\sum \limits _limits_{j i = 1}^k b_{i}a_{j} + \leqslant \sum\limits_{j i = i1}^k a_{n -1}b_{ji} \le leqslant \sum\limits_{j i = 1}^{ik - 1}a_{j} +b_{i}+ \sum\limits_{j = i+1}^{n -1}a_{jx}</tex>, где <tex>1 \dots k</ultex>{{---}} это работы, выполняемые на втором станке во время данного блока.Это неравенство получаем следует из первого случая выбора <tex>J</tex> и из того, что <tex>a_{x} \geqslant a_{i \in J \Rightarrow \ }, \forall j > i, j \in I \Rightarrow \forall j </tex>.Получили, что каждая работа из этого блока начинает выполняться на втором станке позже, чем она заканчивается на первом. Итого мы доказали корректность.<br/> iОптимальность вытекает из того, b_{j} \le a_что <tex>C_{jmax}</tex><ul>не может быть меньше <tex>\sum \limits_{j i = 1}^{in}a_{j} +b_{i}+ a_i,\ \sum\limits_{j i = i+1}^{n -1}a_{j} b_i, \le \sum max \limits_{j i = 1}^{n} a_\{j}</tex></ul>Это неравенство получено из того, что <tex>a_i + b_{i} \le a_{i} \le a_{n}</tex>, где <tex>n = x</tex>а из построения оно равно максимуму из этих значений.</li></ol>Три последовательности выполнения работ, которые мы рассмотрели вначале, являются нижней оценкой для OpenShop problem, следовательно они и дают оптимальное решение.}}

<font color=green>//Функция принимает список из времён выполнения на первом станке a и времён выполнения на втором станке b.<br>//Функция возвращает пару из расписания для первого станка и расписания для второго станка.</font> '''function''' scheduling(a: '''int'''[n], b: '''int[n]'''): '''pair<int[n], int[n]>''' <tex>I = \leftarrow varnothing </tex> <tex>J = \varnothing </tex> <tex>J 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}\leftarrow }\varnothing }</tex> '''for ''' <tex>i = 1 \dots </tex> '''to''' <tex>n</tex> '''if ''' <tex>a_{i} \le bleqslant b_{i}</tex> <tex> I \leftarrow = I \cup \{i\} </tex> '''else''' <tex> J \leftarrow = J \cup \{i\} </tex> Найти <tex>x</tex>, где <tex>a_{x} = \max \limits_{i \in I} \{a_{i}\}</tex> Найти <tex>y</tex>, где <tex>b_{y} = \max \limits_{i \in J} \{b_{i}\}</tex> '''if ''' <tex>a_{x} < > b_{y}</tex> Поменять местами первый и второй станок Пересчитать Начиная с <tex>I, J, x0</tex> Запомнить, что поменяли на первом станке расставляем расписание для <tex>time1 I \setminus \{x\leftarrow 0}</tex> shed2[x] Начиная с <tex>\leftarrow 0</tex> на втором станке расставляем расписание для <tex>time2 \leftarrow b_{x\}</tex> Для всех , затем для <tex>i \in I \setminus \{x\}</tex> sched1[i] <tex>\leftarrow time1<br/tex> От правой границы {{---}} <tex>time1 \leftarrow time1 + a_C_{imax}</tex> на первом станке расставляем расписание для <tex>time2 \leftarrow \max\{time1, time2x\}</tex> sched2[i] , затем для <tex>\leftarrow time2J</tex> От правой границы {{---}} <tex>time2 \leftarrow time2 + b_C_{imax}</tex> Для всех на втором станке расставляем расписание для <tex>i \in J</tex> sched1[i] <tex>\leftarrow time1</tex> <tex>time1 \leftarrow time1 + a_{i}<br/tex> '''pair<tex>time2 \leftarrow \max\{time1int[n], time2\}</tex> sched2int[in] <tex>\leftarrow time2</tex>''' ans = пара из расписания для первого станка и расписания для второго станка <tex>time2 \leftarrow time2 + b_{i}</tex> '''return''' ans '''else''' '''pair<tex>time1 \leftarrow \max\{time1int[n], b_{x}\}</tex> sched1int[xn] <tex>\leftarrow time1</tex> <tex>time1 \leftarrow time1 + a_{x}</tex> <tex>C_{max} \leftarrow \max\{time1''' ans = scheduling(b, time2\}</tex>a) if станки меняли Меняем местамирасписания для станков в ans поменять их обратно '''return''' ans