Задача планування для потокової лінії ( або ) — комбінаторна задача теорії розкладів.
Визначення Дано вимог і машин для їх опрацювання. Задано такі обмеження:
всі вимоги слід опрацювати послідовно на всіх машинах від 1-ї до -ї; будь-яка машина в кожен момент часу може опрацьовувати тільки одну вимогу; не допускаються переривання під час опрацьовування вимог і, отже, розв'язок визначається деякою перестановкою вимог.
Час опрацювання кожної вимоги на кожній машині задано матрицею . Елемент матриці — час опрацювання вимоги на машині .
Зазвичай розглядають такі цільові функції:
, час закінчення опрацювання останньої вимоги на -й машині або загальний час опрацювання; , суму часів закінчення опрацювання вимог на машині .
Алгоритми мінімізації
Алгоритм для двох машин Для розв'язання задачі на двох машинах знайдено поліноміальний за часом алгоритм Джонсона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 машин і кожна з них розв'язується алгоритмом Джонсона.
Примітки