Flow shop — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (правки)
(F2||Cmax)
Строка 18: Строка 18:
  
 
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с <tex>p_{ij} = const</tex> нас интересует порядок выполнения работ только на последнем машине.
 
Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с <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> , приведённой выше.
  
  
Строка 23: Строка 47:
 
* [[Классификация задач]]
 
* [[Классификация задач]]
 
* [[Fpij1sumwu|<tex>F \mid p_{ij} = 1 \mid \sum w_i u_i</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]

Версия 00:19, 22 июня 2012

Эта статья о задачах Flow shop. Для начала дадим определение этого типа задач:

Определение:
Flow shop ([math]F_{m}[/math] в нотации Грэхема): В системе находится m машин, работающих параллельно. Машины упорядочены. Каждая работа должна быть выполнена последовательно на всех машинах с первой по последнюю.


Рассмотрим пример: [math]F \mid p_{ij} = 1 \mid C_{max}[/math]

Допустим у нас [math]n[/math] работ и [math]m[/math] машин. В начальный момент времени мы можем начать обрабатывать любую работу на первом станке. В следующий момент на первом машине можно обрабатывать следующую работу, а на второй перейдёт предыдущая работа с перовой машины. И так далее. Таким образом на выполнение всех работ у нас уйдёт [math]n + m - 1[/math] времени. Проиллюстрируем это диаграммой Гантта для случая [math]n = 6, m = 5[/math]: (по горизонтали время, по вертикали машины, в ячейке номер выполняемой работы)

        0   1   2   3   4   5   6   7   8   9   10
        -------------------------------------------
 M_1   |    1   2   3   4   5   6   -   -   -   -
 M_2   |    -   1   2   3   4   5   6   -   -   -
 M_3   |    -   -   1   2   3   4   5   6   -   -
 M_4   |    -   -   -   1   2   3   4   5   6   -
 M_5   |    -   -   -   -   1   2   3   4   5   6

Заметим, что в данном случае [math]p_{ij}[/math] может быть равно не только единице, но и константе.

Так же, поскольку работа заканчивает выполняться всегда на последней машине, то для решения задач с [math]p_{ij} = const[/math] нас интересует порядок выполнения работ только на последнем машине.

[math]F_2 \mid \mid C_{max}[/math]

Это единственная из flow shop задач с произвольными временами выполнения работ, которая решается за полиномиальное время.

Приведём здесь решение задачи без доказательства, его можно посмотреть в [1].

Оптимальное расписание для первой и второй машины будет совпадать. Таким образом, нам требуется найти перестановку входных работ.

Алгоритм такой: возьмём два пустых списка. Будем рассматривать работы в порядке возрастания [math]min(p_1, p_2)[/math], то есть минимума из времён выполнения данной работы на первой и второй машине. Если у работы [math]p_1 \lt = p_2[/math], то добавим её в конец первого списка. В противном случае добавим её в начало второго списка. Итоговое расписание это конкатенация первого и второго списков.

Псевдокод:

J - множество работ
Head [math] \leftarrow \emptyset [/math]
Tail [math] \leftarrow \emptyset [/math]
while J [math] \ne \emptyset [/math] 
    do
        I [math] \leftarrow [/math] работа с минимальным значением [math]min(p_1, p_2)[/math]
        if [math]p_1 \lt = p_2[/math] Head [math] \leftarrow [/math] Head [math]\circ[/math] I
        else Tail [math] \leftarrow [/math] I [math]\circ[/math] Tail
        J [math] \leftarrow [/math] J [math] \backslash [/math] I
Result [math] \leftarrow [/math] Head [math]\circ[/math] Tail

Обратим внимание, что оптимальное решение задачи [math]F_2 \mid pmtn \mid C_{max}[/math] совпадает с решением задачи [math]F_2 \mid \mid C_{max}[/math] , приведённой выше.


См. также

Литература