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, and 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

Ссылки[править | править вики-текст]

  • Posh Wolf - онлайновый решатель задачи flow shop с визуализацией в режиме реального времени