Flow shop

Эта статья о задачах 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] нас интересует порядок выполнения работ только на последнем машине, и таким образом задачу можно свести к задаче об одной машине.

Задачи с произвольно заданными временами выполнения работ почти все являются NP-полными и решаются приближённо в случае необходимости.

[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] , приведённой выше.

См. также

• Классификация задач
• [math]F \mid p_{ij} = 1 \mid \sum w_i u_i[/math]

Литература

• [1]Scheduling Algorithms, Peter Brucker