1632
правки
Изменения
м
Алгоритм такойОбозначим за <tex>p_1</tex> время выполнения работы на первом станке, за <tex>p_2</tex> время выполнения работы на втором станке. Будем использовать следующий алгоритм: возьмём два пустых списка и будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
'''return''' <tex>\mathrmmathtt{Result} = \mathrm{FirstListList1} \cup \mathrmmathtt{SecondListList2} </tex>
rollbackEdits.php mass rollback
Заметим, что в данном случае <tex>p_{ij}</tex> может быть равно не только единице, но и любой константе.
{{УтверждениеТеорема
|statement = Любая задача вида <tex>F \mid p_{ij} = 1 \mid ? </tex> сводится к соответствующей задаче вида <tex>1 \mid p_{ij} = 1 \mid ?</tex>.
|proof =
}}
Примером применения этого утверждения этой теоремы может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex>]].
Задачи с произвольными временами выполнения работ почти все являются [[NP Классы_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> Его можно посмотреть тут Доказательство описано в книге [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>.
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
===Алгоритм===
===Псевдокод===
Для представления работы в памяти будем использовать следующую структуру: '''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> \mathrmmathtt{FirstListList1}</tex> и , <tex> \mathrmmathtt{SecondListList2} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ. <font color = green>// Функция принимает список работ J и возвращает список с расписанием работ.</font> '''function''' scheduling(<tex>J</tex>: '''List<Job>'''): '''List<int>''' <tex>\mathrmmathtt{FirstListList1} = \varnothing </tex> <tex>\mathrmmathtt{SecondListList2} = \varnothing </tex> '''while''' J <tex> J \ne \varnothing </tex> I <tex> = I</tex> = работа с минимальным значением <tex>\min(p_1, \ \ p_2)</tex>
'''if''' <tex>p_1 \leqslant p_2</tex>
<tex>\mathrmmathtt{FirstListList1} = \mathrmmathtt{FirstListList1} \cup I </tex>
'''else'''
<tex>\mathrmmathtt{SecondListList2} = I \cup \mathrmmathtt{SecondListList2} </tex>
<tex>J = J \setminus I </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>C_{max}</tex>, что и требовалось доказать.}}
== См. также ==
