Задача планування для потокової лінії

Задача планування для потокової лінії (англ. flow shop scheduling problem або permutation flowshop scheduling^[1]) — комбінаторна задача теорії розкладів.

Дано ${\displaystyle n}$ вимог і ${\displaystyle m}$ машин для їх опрацювання. Задано такі обмеження:

• всі вимоги слід опрацювати послідовно на всіх машинах від 1-ї до ${\displaystyle m}$-ї;
• будь-яка машина в кожен момент часу може опрацьовувати тільки одну вимогу;
• не допускаються переривання під час опрацьовування вимог і, отже, розв'язок визначається деякою перестановкою вимог.

Час опрацювання кожної вимоги на кожній машині задано матрицею ${\displaystyle M_{nm}(\mathbb {R} ^{+})}$. Елемент матриці ${\displaystyle p_{ij}}$ — час опрацювання вимоги ${\displaystyle i}$ на машині ${\displaystyle j}$.

Зазвичай розглядають такі цільові функції:

• ${\displaystyle C_{max}}$, час закінчення опрацювання останньої вимоги на ${\displaystyle m}$-й машині або загальний час опрацювання;
• ${\displaystyle \Sigma _{i=1}^{n}c_{i}}$, суму часів закінчення опрацювання вимог на машині ${\displaystyle m}$.

Для розв'язання задачі на двох машинах знайдено поліноміальний за часом алгоритм Джонсона^[2]: вимоги ділять на дві множини ${\displaystyle U=\{i:p_{i1}<p_{i2}\}}$ і ${\displaystyle V=\{i:p_{i1}\geq p_{i2}\}}$, далі:

• вимоги ${\displaystyle U}$ впорядковують за неспаданням ${\displaystyle p_{i1}}$,
• вимоги ${\displaystyle V}$ впорядковують за незростанням ${\displaystyle p_{i2}}$,
• оптимальна послідовність є конкатенацією впорядкованих таким чином ${\displaystyle U}$ і ${\displaystyle V}$.

Алгоритм має часову складність ${\displaystyle n\log(n)}$, оскільки використовує алгоритм сортування.

У разі більше двох машин задача є NP-складною, але розроблено багато евристичних поліноміальних за часом наближених алгоритмів^[3].

Одним з найвідоміших алгоритмів є евристика Наваза, Енскора і Гама (Nawaz, Enscore, Ham)^[4]:

• вимоги упорядковують за ${\displaystyle \sum _{j=1}^{m}p_{ij}}$ і нумерують відповідно до цього порядку,
• визначають порядок опрацювання двох перших вимог так, щоб мінімізувати час їх опрацювання,
• для ${\displaystyle i=3}$ до ${\displaystyle n}$:
  • вимога ${\displaystyle i}$ поміщається на позицію ${\displaystyle k\in [1,i]}$, яка мінімізує загальний час обслуговування перших ${\displaystyle i}$ вимог
• (кінець циклу)

Відома також евристика Кемпбелла, Дудека і Сміта (Campbell, Dudek, Smith), в якій задача для ${\displaystyle m}$ машин послідовно зводиться до ${\displaystyle m-1}$ задачі для 2 машин^[5] і кожна з них розв'язується алгоритмом Джонсона.