Участник:МетаСкептик12/Черновик

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$.

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

Далее рассматриваются алгоритмы минимизации общего времени обслуживания.

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

Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона.

Разделим требования на два множества $U=\{i:p_{i1}<p_{i2}\}$ et $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, and Smith). Задача для $m$ машин последовательно сводится к $m-1$ задаче для 2 машин. Каждая из них решается алгоритмом Джонсона.