Задача планирования для поточной линии

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Flow shop scheduling problem»)
Перейти к: навигация, поиск

Задача планирования для поточной линии (англ. 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
  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