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

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

Визначення

Дано ${\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}$.

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

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

Для розв'язання задачі на двох машинах знайдено поліноміальний за часом алгоритм Джонсона: вимоги ділять на дві множини ${\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-складною, але розроблено багато евристичних поліноміальних за часом наближених алгоритмів.

Евристика NEH

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

• вимоги упорядковують за ${\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 машин і кожна з них розв'язується алгоритмом Джонсона.

Примітки

1. (PDF). Архів оригіналу (PDF) за 6 травня 2021. Процитовано 18 травня 2021.
2. S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.
3. A comprehensive review and evaluation of permutation flowshop heuristics
4. [1] A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
5. (PDF). Архів оригіналу (PDF) за 21 жовтня 2014. Процитовано 22 квітня 2013.