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

Задача планування для потокової лінії (Шаблон:Lang-en або Шаблон:Lang-en2) — комбінаторна задача теорії розкладів.

Визначення

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

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

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

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

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

Алгоритми мінімізації $C_{max}$

Алгоритм для двох машин

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

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

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

Алгоритми для трьох і більше машин

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

Евристика NEH

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

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

Евристика Кемпбелла, Дудека і Сміта

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