3622
правки
Изменения
→Псевдокод
Это единственная из 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''' p1 <tex>p_1</tex> <font color = green>// Время выполнения на первом станке</font> '''int''' p2 <tex>p_2</tex> <font color = green>// Время выполнения на втором станке</font>
Приведём реализацию самого алгоритма:
<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(p1p_1, \ \ p2p_2)</tex> '''if''' <tex>p1 p_1 \leqslant p2p_2</tex>
<tex> \mathtt{List1} = \mathtt{List1} \cup I </tex>
'''else'''
