Задача планирования для поточной линии ( или ) — комбинаторная задача теории расписаний.
В стандартной 3-позиционной нотации для задач расписания работ вариант поточной линии обозначается буквой F в первом поле. Например, задача, обозначаемая как F3||, представляет собой задачу планирования поточной линии с тремя машинами и единичным временем обработки, где целью является минимизация максимального времени завершения.
Определение Даны требований и машин для их обработки. Заданы следующие ограничения: все требования должны пройти обработку последовательно на всех машинах с 1-й до -ой; любая машина в каждый момент времени может обрабатывать только одно требование. не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.
Задано время обслуживания каждого требования на каждой машине матрицей . Элемент матрицы — время обслуживания требования на машине .
Обычно рассматривают следующие целевые функции: , время окончания обслуживания последнего требования на -ой машине или общее время обслуживания; , сумму времен окончания обслуживания требований на машине .
Алгоритмы минимизации Cmax Алгоритм для двух машин Для решения задачи на двух машинах найден полиномиальный по времени алгоритм ДжонсонаS.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.: требования разделяются на два множества и , далее: требования упорядочиваются по неубыванию , требования упорядочиваются по невозрастанию , оптимальная последовательность является конкатенацией упорядоченных таким образом и .
Алгоритм имеет временную сложность , поскольку использует алгоритм сортировки.
Алгоритмы для трёх и более машин В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмовA comprehensive review and evaluation of permutation flowshop heuristics.
Эвристика NEH Одним из наиболее известных алгоритмов является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem: требования упорядочиваются по и нумеруются в соответствии с этим порядком, определяется порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания, для до : помещается требование на позицию , которая минимизирует общее время обслуживания первых требований (конец цикла)
Эвристика Кэмпбелла, Дудека и Смита Известна также эвристика Кэмпбелла, Дудека и Смита (Campbell, Dudek, Smith), в которой задача для машин последовательно сводится к задаче для 2 машин и каждая из них решается алгоритмом Джонсона.
Примечания
Категория:Алгоритмы Категория:Решение задач