Эта статья о задачах Flow shop. Для начала дадим определение этого типа задач:{{Определение|definition == Описание =='''Flow shop''' ('''Рассмотрим пример: <tex>F_F \mid p_{ij} = 1 \mid C_{mmax}</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!!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>F \mid p_{ij} M_3</tex>|—|—|1|2|3|4|5|6|—|—|-align= "center"!<tex>M_4</tex>|—|—|—|1 \mid C_{max}|2|3|4|5|6|—|-align="center"!<tex>M_5</tex>|—|—|—|—|1|2|3|4|5|6|}
Допустим у нас Заметим, что в данном случае <tex>np_{ij}</tex> работ может быть равно не только единице, но и любой константе. {{Теорема|statement = Любая задача вида <tex>mF \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex> машин. В начальный момент времени мы можем начать обрабатывать любую работу |proof = Поскольку работа всегда заканчивает выполняться на первом станке. В следующий момент на первом последней машине можно обрабатывать следующую работу, а нас интересуют только времена завершения работ на второй перейдёт предыдущая работа с перовой машиныпоследней машине. И так далее. Таким образом на выполнение всех работ у нас уйдёт Также очевидно, что последняя машина может начать работать только в момент времени <tex>n + m - 1</tex> времени. Проиллюстрируем это диаграммой Гантта для случая Оказывается, что любое решение задачи <tex>n 1 \mid p_{ij} = 61 \mid ? </tex> с дедлайнами, уменьшенными на <tex> m = 5- 1 </tex>: (по горизонтали время, по вертикали машины, можно преобразовать в ячейке номер выполняемой работы) '''0 оптимальное расписание для задачи <tex>F \mid p_{ij} = 1 2 3 4 5 6 7 8 9 10''' ------------------------------------------- '''M_1''' | 1 2 3 4 5 6 - - - - '''M_2''' | - 1 2 3 4 5 6 - - - '''M_3''' | - - 1 2 3 4 5 6 - - '''M_4''' | - - - 1 2 3 4 5 6 - '''M_5''' | - - - - 1 2 3 4 5 6\mid ? </tex>. Докажем это.
ЗаметимВозьмем оптимальное расписание для соответствующей задачи с одним станком, что выполним работы в данном случае этом порядке на первой машине, затем на второй машине, начиная с момента времени <tex> 1 </tex>p_{ij}, и так далее, до выполнения на последней машине, начиная с <tex> m - 1 </tex> может быть равно не только единице. Это расписание корректно и соблюдает все дедлайны. Поскольку целевая функция совпадает с соответствующей функцией для задачи на одном станке, но оно оптимально и константедля данной задачи.}}
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с Примером применения этой теоремы может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = const1 \mid \sum w_iu_i</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> ==
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.
Приведём здесь решение задачи без доказательства, его можно посмотреть <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>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков. ===Псевдокод===Для представления работы в памяти будем использовать следующую структуру: '''struct''' Job: '''int''' <tex>p_1</tex> <font color = green>// Время выполнения на первом станке</font> '''int''' <tex>p_2</tex> <font color = green>// Время выполнения на втором станке</font> Приведём реализацию самого алгоритма:*<tex> \mathtt{J}</tex> {{---}} список работ, которые надо выполнить,*<tex> \mathtt{List1}</tex>, <tex> \mathtt{List2} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ. <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>\min(p_1, \ \ p_2)</tex> '''if''' <tex>p_1 \leqslant p_2</tex> <tex> \mathtt{List1} = \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>min(p_1, p_2)2 </tex>или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в тот момент, когда начинается второй промежуток, то есть минимума из времён выполнения данной при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на первой машинах по-прежнему не пересекаются, и каждая работа на второй машине. Если у работы делается после того, как она сделана на первой: работа <tex>p_1 <= p_2J </tex>может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то добавим её в конец первого списка. В противном случае добавим её в начало есть уже после конца второго спискапромежутка; а время окончания выполнения остальных работ на первой машине неувеличилось. Итоговое расписание это конкатенация первого и второго списковВажно, что подобная операция не увеличивает <tex> C_{max} </tex>.
Псевдокод: J - множество работ Head <tex> \leftarrow \emptyset </tex> Tail <tex> \leftarrow \emptyset </tex> '''while''' J <tex> \ne \emptyset </tex> '''do''' I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1Будем повторять эту операцию до тех пор, p_2)</tex> '''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I '''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail J <tex> \leftarrow </tex> J <tex> \backslash </tex> I Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tailпока на первой машине все работы не станут выполняться без прерываний. Так как количество прерываний конечно, а такая операция уменьшает их количество на один, этот процесс конечен.
Обратим вниманиеТеперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, что оптимальное решение задачи <tex>F_2 \mid pmtn \mid C_{max}</tex> совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex> разбитую на два или более промежутка. Передвинем более поздний промежуток к концу более раннего, приведённой вышеа работы между ними сдвинем вправо. Доказательство корректности измененного расписания аналогично доказательству для первой машины. Будем повторять данную операцию, пока на второй машине присутствуют прерывания.
Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение <tex>C_{max}</tex>.}}
== См. также ==
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</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Теория расписаний]]
