Задача планирования для поточной линии (англ. flow shop scheduling problem или permutation flowshop scheduling[1]) — комбинаторная задача теории расписаний.
Определение
Даны требований и машин для их обработки. Заданы следующие ограничения:
- все требования должны пройти обработку последовательно на всех машинах с 1-й до -ой;
- любая машина в каждый момент времени может обрабатывать только одно требование.
- не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.
Задано время обслуживания каждого требования на каждой машине матрицей . Элемент матрицы — время обслуживания требования на машине .
Обычно рассматривают следующие целевые функции:
- , время окончания обслуживания последнего требования на -ой машине или общее время обслуживания;
- , сумму времен окончания обслуживания требований на машине .
Алгоритмы минимизации
Алгоритм для двух машин
Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона[2]: требования разделяются на два множества и , далее:
- требования упорядочиваются по неубыванию ,
- требования упорядочиваются по невозрастанию ,
- оптимальная последовательность является конкатенацией упорядоченных таким образом и .
Алгоритм имеет временную сложность , поскольку использует алгоритм сортировки.
Алгоритмы для трёх и более машин
В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмов[3].
Эвристика NEH
Одним из наиболее известных алгоритмов является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)[4]:
- требования упорядочиваются по и нумеруются в соответствии с этим порядком,
- определяется порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания,
- для до :
- помещается требование на позицию , которая минимизирует общее время обслуживания первых требований
- (конец цикла)
Эвристика Кэмпбелла, Дудека и Смита
Известна также эвристика Кэмпбелла, Дудека и Смита (Campbell, Dudek, Smith), в которой задача для машин последовательно сводится к задаче для 2 машин[5] и каждая из них решается алгоритмом Джонсона.
Примечания