42
правки
Изменения
F2||Cmax
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с <tex>p_{ij} = const</tex> нас интересует порядок выполнения работ только на последнем машине.
== <tex>F_2 \mid \mid C_{max}</tex> ==
Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.
Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].
Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти перестановку входных работ.
Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания <tex>min(p_1, p_2)</tex>, то есть минимума из времён выполнения данной работы на первой и второй машине. Если у работы <tex>p_1 <= p_2</tex>, то добавим её в конец первого списка. В противном случае добавим её в начало второго списка. Итоговое расписание это конкатенация первого и второго списков.
Псевдокод:
J - множество работ
Head <tex> \leftarrow \emptyset </tex>
Tail <tex> \leftarrow \emptyset </tex>
'''while''' J <tex> \ne \emptyset </tex>
'''do'''
I <tex> \leftarrow </tex> работа с минимальным значением <tex>min(p_1, p_2)</tex>
'''if''' <tex>p_1 <= p_2</tex> Head <tex> \leftarrow </tex> Head <tex>\circ</tex> I
'''else''' Tail <tex> \leftarrow </tex> I <tex>\circ</tex> Tail
J <tex> \leftarrow </tex> J <tex> \backslash </tex> I
Result <tex> \leftarrow </tex> Head <tex>\circ</tex> Tail
Обратим внимание, что оптимальное решение задачи <tex>F_2 \mid pmtn \mid C_{max}</tex> совпадает с решением задачи <tex>F_2 \mid \mid C_{max}</tex> , приведённой выше.
* [[Классификация задач]]
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</tex>]]
== Литература ==
*[1][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]
