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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення[ред. | ред. код]

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

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

Час опрацювання кожної вимоги на кожній машині задано матрицею . Елемент матриці  — час опрацювання вимоги на машині .

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

  • , час закінчення опрацювання останньої вимоги на -й машині або загальний час опрацювання;
  • , суму часів закінчення опрацювання вимог на машині .

Алгоритми мінімізації [ред. | ред. код]

Алгоритм для двох машин[ред. | ред. код]

Для розв'язання задачі на двох машинах знайдено поліноміальний за часом алгоритм Джонсона[2]: вимоги ділять на дві множини і , далі:

  • вимоги впорядковують за неспаданням ,
  • вимоги впорядковують за незростанням ,
  • оптимальна послідовність є конкатенацією впорядкованих таким чином і .

Алгоритм має часову складність , оскільки використовує алгоритм сортування.

Алгоритми для трьох і більше машин[ред. | ред. код]

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

Евристика NEH[ред. | ред. код]

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

  • вимоги упорядковують за і нумерують відповідно до цього порядку,
  • визначають порядок опрацювання двох перших вимог так, щоб мінімізувати час їх опрацювання,
  • для до :
    • вимога поміщається на позицію , яка мінімізує загальний час обслуговування перших вимог
  • (кінець циклу)

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

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

Примітки[ред. | ред. код]

  1. Permutation flowshop problem (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. Chapter_4, Flow Shop Scheduling (PDF). Архів оригіналу (PDF) за 21 жовтня 2014. Процитовано 22 квітня 2013.