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

Flow shop scheduling problem (планирование текущего обслуживания) это комбинаторная задача теории расписаний.

Определение

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

Эвристика Наваз-Энскор-Хам (Nawaz-Enscore-Ham) (NEH)

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

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

Задачу для m машин последовательно сводим к m-1 задаче для 2 машин.