Изменения

Дадим определение этого типа задач:{{Определение|definition ='''Flow shop''' ('''<tex>F_{m}</tex>''' в нотации Грэхема): В системе находится m машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.}}= Описание ==

Допустим, у нас <tex>n</tex> работ и <tex>m</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу на первой машине. В следующий момент на первой машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с первой машины, и так далее. Таким образом, на выполнение всех работ у нас уйдёт <tex>n + m - 1</tex> единиц времени. Проиллюстрируем это диаграммой Ганта Гантта для случая <tex>n = 6, m = 5</tex>: (по горизонтали время, по вертикали машины, в ячейке — номер выполняемой работы) '''{| class = "wikitable" style="width: 55%; height: 200px"! !!0 !!1 !!2 !!3 4 !!5 !!6 !!7 !!8 !!9 !!10''' ------------------------------------------|-align="center" '''!<tex>M_1''' </tex>| 1 |2 |3 |4 |5 |6 - - - |—|—|—|—|-align="center" '''!<tex>M_2''' </tex>|—| - 1 |2 |3 |4 |5 |6 - - |—|—|—|-align="center" '''!<tex>M_3''' </tex>|—|—| - - 1 |2 |3 |4 |5 |6 - |—|—|-align="center" '''!<tex>M_4''' </tex>|—|—|—| - - - 1 |2 |3 |4 |5 |6 |—|-align="center" '''!<tex>M_5''' </tex>|—|—|—|—| - - - - 1 |2 |3 |4 |5 |6|}

Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе. {{Теорема|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>. |proof = Поскольку работа всегда заканчивает выполняться на последней машине, нас интересуют только времена завершения работ на последней машине. Также очевидно, что последняя машина может начать работать только в момент времени <tex> m - 1 </tex>. Оказывается, что любое решение задачи <tex> 1 \mid p_{ij} = 1 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m - 1 </tex> можно преобразовать в оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 \mid ? </tex>. Докажем это.

Так жеВозьмем оптимальное расписание для соответствующей задачи с одним станком, выполним работы в этом порядке на первой машине, поскольку работа заканчивает выполняться всегда затем на последней второй машине, для решения задач начиная с момента времени <tex>p_{ij} = const1 </tex> нас интересует порядок , и так далее, до выполнения работ только на последнем последней машине. {{Утверждение|statement = Задачи вида <tex>F | p_{ij} = const | ?</tex> можно сводить к задачам вида , начиная с <tex>m - 1 | p_{ij} = const | ?</tex> . Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, оно оптимально и для данной задачи.}}

Задачи с произвольно заданными произвольными временами выполнения работ почти все являются [[Классы_NP,_coNP,_Σ₁,_Π₁#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F.2C_.D1.81.D0.B2.D1.8F.D0.B7.D1.8C_.CE.A3.E2.82.81_.D0.B8_NP | NP-трудными и решаются приближённо в случае необходимости]].

== Задача Джонсона о двух станках <tex>F_2 \mid \mid C_{max}</tex> ==

Приведём здесь решение задачи без доказательства, его можно посмотреть <ref> Доказательство описано в книге [1http://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter Brucker]на страницах 174 {{---}} 178.</ref>.

Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти перестановку входных работпорядок, в котором будут выполняться работы на каждой машине.

===Алгоритм такой===Обозначим за <tex>p_1</tex> время выполнения работы на первом станке, за <tex>p_2</tex> время выполнения работы на втором станке. Будем использовать следующий алгоритм: возьмём два пустых списка. Будем и будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 <= \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.

===Псевдокод===Для представления работы в памяти будем использовать следующую структуру: J - множество работ Head <tex> \leftarrow \emptyset </tex> Tail <tex> \leftarrow \emptyset </tex> '''whilestruct''' J <tex> \ne \emptyset </tex> Job: '''doint''' I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex> '''if''' <texfont color = green>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circВремя выполнения на первом станке</texfont> I '''elseint''' Tail <tex> \leftarrow p_2</tex> I <tex>\circ</tex> Tail J <texfont color = green> \leftarrow </tex> J <tex> \backslash </tex> I Result <tex> \leftarrow </tex> Head <tex>\circВремя выполнения на втором станке</texfont> Tail

<font color = green>// Функция принимает список работ J и возвращает список с расписанием работ.</font> '''function''' scheduling(<tex>J</tex>: '''List<Job>'''): '''List<int>''' <tex> \mathtt{List1} = \varnothing </tex> <tex>\mathtt{List2} =\varnothing </tex> '''while''' <tex>J \ne \varnothing </tex> <tex>I</tex> = работа с минимальным значением <tex>F_2 \mid pmtn min(p_1, \ \mid C_p_2)</tex> '''if''' <tex>p_1 \leqslant p_2</tex> <tex> \mathtt{maxList1}= \mathtt{List1} \cup I </tex> '''else''' <tex>\mathtt{List2} =I \cup \mathtt{List2} </tex> <tex>J =J \setminus I </tex> '''return''' <tex>\mathtt{List1} \cup \mathtt{List2} </tex>

== Задача Джонсона о двух станках с прерываниями <tex>F_2 \mid pmtn \mid C_{max}</tex> =={{Теорема|statement= Оптимальное решение этой задачи совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex> , приведённой выше. Докажем |proof = Пусть у нас есть оптимальное расписание для задачи <tex>F_2 \mid pmtn \mid C_{max}</tex>. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при этозначение <tex>C_{max}</tex> .

Пусть у нас есть оптимальное расписание для задачи Рассмотрим первую машину. Допустим, что некоторая работа <tex> J </tex> выполняется в <tex> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по-прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex>F_2 \mid pmtn \mid C_{max}J </tex>может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а время окончания выполнения остальных работ на первой машине неувеличилось. ПокажемВажно, что его за конечное число шагов можно преобразовать к расписанию без прерываний, подобная операция не изменив при это значение увеличивает <tex>C_{max}</tex> .

Рассмотрим первую машину. Допустим, что некоторая работа J выполняется в 2 разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в том момент, когда мы начинается второй промежуток. Таким образом работа J станет выполняться без прерывания. При этом работы, которые были между промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа J может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а остальные работы были сдвинуты влево, наложений точно не возникнет.Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.

Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Расписание останется корректным по аналогичным причинамДоказательство корректности измененного расписания аналогично доказательству для первой машины. Повторим Будем повторять данную операцию. Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex> , так как мы только меняли порядок выполнения работ, что и требовалось доказатьпока на второй машине присутствуют прерывания.

== Литература Примeчания==*<references/> [[1Категория: Дискретная математика и алгоритмы]][http[Категория://books.google.ru/books?id=FrUytMqlCv8C&printsec=frontcover&dq=scheduling+algorithms&hl=ru&sa=X&ei=0MPMT4HqKYSk4gSBm6gp&sqi=2&ved=0CDEQ6AEwAA#v=onepage&q=scheduling%20algorithms&f=false Scheduling Algorithms, Peter BruckerТеория расписаний]]