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 | p_{ij} = const | ?[/math] можно сводить к задачам вида [math]1 | 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_2 \mid pmtn \mid C_{max}[/math]. Покажем, что его за конечное число шагов можно преобразовать к расписанию без прерываний, не изменив при это значение [math]C_{max}[/math] .

Рассмотрим первую машину. Допустим, что некоторая работа J выполняется в 2 разных промежутка времени. Тогда передвинем более ранний промежуток вправо по оси времени так, чтоб он заканчивался в том момент, когда мы начинается второй промежуток. Таким образом работа J станет выполняться без прерывания. При этом работы, которые были между промежутками, сдвинем влево на длину первого промежутка. Расписание при этом осталось корректным, так как работы на машинах по прежнему не пересекаются, и каждая работа на второй машине делается после того, как она сделана на первой: работа J может начать выполняться на второй машине только после того, как она целиком выполнится на первой, то есть уже после конца второго промежутка; а остальные работы были сдвинуты влево, наложений точно не возникнет. Будем повторять эту операцию до тех пор, пока на первой машине все работы не станут выполняться без прерываний.

Теперь избавимся от прерываний на второй машине. Точно так же рассмотрим работу, разбитую на два промежутка. Передвинем более поздний промежуток к концу более раннего, а работы между ними сдвинем вправо. Расписание останется корректным по аналогичным причинам. Повторим операцию.

Таким образом, мы получили корректное расписание без прерываний, не изменив при этом значение [math]C_{max}[/math] , так как мы только меняли порядок выполнения работ, что и требовалось доказать.

См. также

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

Литература

• [1]Scheduling Algorithms, Peter Brucker