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

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

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

Определение[править | править вики-текст]

Даны n требований и m машин для их обработки. Заданы следующие ограничения:

  • все требования должны пройти обработку последовательно на всех машинах с 1-й до m-ой;
  • любая машина в каждый момент времени может обрабатывать только одно требование.
  • не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.

Задано время обслуживания каждого требования на каждой машине матрицей M_{nm}(\mathbb{R}^{+}). Элемент матрицы p_{ij} — время обслуживания требования i на машине j.

Обычно рассматривают следующие целевые функции:

  • C_{max}, время окончания обслуживания последнего требования на m-ой машине или общее время обслуживания;
  • \Sigma^{n}_{i=1} c_i, сумму времен окончания обслуживания требований на машине m.

Алгоритмы минимизации C_{max}[править | править вики-текст]

Алгоритм для двух машин[править | править вики-текст]

Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона[2]: требования разделяются на два множества U = \{i : p_{i1} < p_{i2}\} и V = \{i : p_{i1} \geq p_{i2}\}, далее:

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

Алгоритм имеет временную сложность n \log(n), поскольку использует алгоритм сортировки.

Алгоритмы для трёх и более машин[править | править вики-текст]

В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмов[3].

Эвристика NEH[править | править вики-текст]

Одним из наиболее известных алгоритмов является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)[4]:

  • требования упорядочиваются по  \sum_{j=1}^{m} p_{ij} и нумерюутся в соответствии с этим порядком,
  • определяется порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания,
  • для i = 3 до n:
    • помещается требование i на позицию k \in [1,i], которая минимизирует общее время обслуживания первых  i требований
  • (конец цикла)

Эвристика Кэмпбелла, Дудека и Смита[править | править вики-текст]

Известна также эвристика Кэмпбелла, Дудека и Смита (Campbell, Dudek, Smith), в которой задача для m машин последовательно сводится к m-1 задаче для 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