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

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

Определение

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

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

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

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

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

Алгоритмы минимизации $C_{max}$

Алгоритм для двух машин

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

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

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

Алгоритмы для трёх и более машин

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

Эвристика NEH

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

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

Эвристика Кэмпбелла, Дудека и Смита

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