Задача планирования для поточной линии

Задача планирования для поточной линии (англ. flow shop scheduling problem или permutation flowshop scheduling^[1]) — комбинаторная задача теории расписаний.

Даны ${\displaystyle n}$ требований и ${\displaystyle m}$ машин для их обработки. Заданы следующие ограничения:

• все требования должны пройти обработку последовательно на всех машинах с 1-й до ${\displaystyle m}$-ой;
• любая машина в каждый момент времени может обрабатывать только одно требование.
• не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.

Задано время обслуживания каждого требования на каждой машине матрицей ${\displaystyle M_{nm}(\mathbb {R} ^{+})}$. Элемент матрицы ${\displaystyle p_{ij}}$ — время обслуживания требования ${\displaystyle i}$ на машине ${\displaystyle j}$.

Обычно рассматривают следующие целевые функции:

• ${\displaystyle C_{max}}$, время окончания обслуживания последнего требования на ${\displaystyle m}$-ой машине или общее время обслуживания;
• ${\displaystyle \Sigma _{i=1}^{n}c_{i}}$, сумму времен окончания обслуживания требований на машине ${\displaystyle m}$.

Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона^[2]: требования разделяются на два множества ${\displaystyle U=\{i:p_{i1}<p_{i2}\}}$ и ${\displaystyle V=\{i:p_{i1}\geq p_{i2}\}}$, далее:

• требования ${\displaystyle U}$ упорядочиваются по неубыванию ${\displaystyle p_{i1}}$,
• требования ${\displaystyle V}$ упорядочиваются по невозрастанию ${\displaystyle p_{i2}}$,
• оптимальная последовательность является конкатенацией упорядоченных таким образом ${\displaystyle U}$ и ${\displaystyle V}$.

Алгоритм имеет временную сложность ${\displaystyle n\log(n)}$, поскольку использует алгоритм сортировки.

В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмов^[3].

Одним из наиболее известных алгоритмов является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)^[4]:

• требования упорядочиваются по ${\displaystyle \sum _{j=1}^{m}p_{ij}}$ и нумеруются в соответствии с этим порядком,
• определяется порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания,
• для ${\displaystyle i=3}$ до ${\displaystyle n}$:
  • помещается требование ${\displaystyle i}$ на позицию ${\displaystyle k\in [1,i]}$, которая минимизирует общее время обслуживания первых ${\displaystyle i}$ требований
• (конец цикла)

Известна также эвристика Кэмпбелла, Дудека и Смита (Campbell, Dudek, Smith), в которой задача для ${\displaystyle m}$ машин последовательно сводится к ${\displaystyle m-1}$ задаче для 2 машин^[5] и каждая из них решается алгоритмом Джонсона.