251
правка
Изменения
Нет описания правки
Примером применения этого утверждения может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \mid \sum w_iu_i</tex>]].
Задачи с произвольными временами выполнения работ почти все являются [[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] </ref>.
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти порядок, в котором будут выполняться работы на каждой машине.
===Алгоритм===Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>\min(p_1, p_2)</tex>, то есть, минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 \leqslant p_2</tex>, то добавим её в конец первого списка. В противном случае, добавим её в начало второго списка. Итоговое расписание — это конкатенация первого и второго списков.
===Псевдокод:===
<tex> Head = \varnothing </tex>
<tex>Tail = \varnothing </tex>
<font color = green>//J - множество работ</font>
'''while''' J <tex> \ne \varnothing </tex>
I <tex> = </tex> работа с минимальным значением <tex>\min(p_1, p_2)</tex>
'''if''' <tex>p_1 \leqslant p_2</tex>
<tex>Head = {Head } \cup I </tex>
