3622
правки
Изменения
→Псевдокод
Примером применения этой теоремы может служить следующая [[Fpij1sumwu|задача: <tex>F \mid p_{ij} = 1 \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> Доказательство описано тут в книге [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>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> \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> ==
