1632
правки
Изменения
м
rollbackEdits.php mass rollback
Это единственная из 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> \mathtt{List1}</tex>, <tex> \mathtt{List2} </tex> {{---}} списки, в которые будем записывать порядок выполнения работ.
<font color = green>//Функция принимает список работ J и возвращает список с расписанием работ.</font> '''function''' scheduling(<tex>J</tex>: '''List<int[2]Job>'''): '''List<int>'''
<tex> \mathtt{List1} = \varnothing </tex>
<tex>\mathtt{List2} = \varnothing </tex>
'''while''' <tex>J \ne \varnothing </tex>
<tex>I </tex> = работа с минимальным значением <tex>\min(p[1]p_1, \ \ p[2]p_2)</tex> '''if''' <tex>p[1] p_1 \leqslant p[2]p_2</tex>
<tex> \mathtt{List1} = \mathtt{List1} \cup I </tex>
'''else'''
