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

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

ОпределениеПравить

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

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

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

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

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

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

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

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

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

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

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

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

Эвристика NEHПравить

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

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

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

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