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

Для розв'язання задачі на двох машинах знайдено поліноміальний за часом алгоритм Джонсона[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] і кожна з них розв'язується алгоритмом Джонсона.