Изменения

Дадим определение этого типа задач:{{Определение|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> ==

Приведём здесь решение задачи без доказательства, его можно посмотреть <ref> Доказательство описано в книге [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] на страницах 174 {{---}} 178.</ref>.

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

Псевдокод: J - множество работ===Алгоритм=== Head Обозначим за <tex> \leftarrow \emptyset p_1</tex> Tail время выполнения работы на первом станке, за <tex> \leftarrow \emptyset </tex> '''while''' J <tex> \ne \emptyset p_2</tex> время выполнения работы на втором станке. '''do''' I Будем использовать следующий алгоритм: возьмём два пустых списка и будем рассматривать работы в порядке возрастания <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex> '''if''' , то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 <= \leqslant 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 mathtt{J}</tex> {{---}} список работ, которые надо выполнить,*<tex> \mid C_mathtt{maxList1}</tex> ==, <tex> \mathtt{List2} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ.

Оптимальное решение этой задачи совпадает <font color = green>// Функция принимает список работ J и возвращает список с решением задачи расписанием работ.</font> '''function''' scheduling(<tex>J</tex>: '''List<Job>'''): '''List<int>''' <tex>F_2 \mid mathtt{List1} = \mid C_varnothing </tex> <tex>\mathtt{maxList2}= \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> 2 </tex> или более разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в том тот момент, когда мы начинается второй промежуток. Таким образом работа J станет выполняться без прерывания. При , при этом работы, которые были между этими двумя промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по -прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа <tex> J </tex> может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а остальные работы были сдвинуты влево, наложений точно не возникнетвремя окончания выполнения остальных работ на первой машине неувеличилось.Будем повторять эту операцию до тех порВажно, пока на первой машине все работы что подобная операция не станут выполняться без прерыванийувеличивает <tex> C_{max} </tex>.

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

Таким образом, мы получили корректное расписание без Теперь избавимся от прерыванийна второй машине. Точно так же рассмотрим работу, не изменив при этом значение <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Теория расписаний]]