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

Определение

Даны ${\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}$ .

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

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

Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона : требования разделяются на два множества ${\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-трудной , но разработано множество эвристических полиномиальных по времени приближённых алгоритмов .

Эвристика NEH

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

• требования упорядочиваются по ${\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 машин и каждая из них решается алгоритмом Джонсона.

Примечания