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

См. также

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