Русская Википедия:Задача планирования для поточной линии
Задача планирования для поточной линии (Шаблон:Lang-en или Шаблон:Lang-en2[1]) — комбинаторная задача теории расписаний.
Определение
Даны <math>n</math> требований и <math>m</math> машин для их обработки. Заданы следующие ограничения:
- все требования должны пройти обработку последовательно на всех машинах с 1-й до <math>m</math>-ой;
- любая машина в каждый момент времени может обрабатывать только одно требование.
- не допускаются прерывания при обслуживании требований и, следовательно, решение определяется некоторой перестановкой требований.
Задано время обслуживания каждого требования на каждой машине матрицей <math>M_{nm}(\mathbb{R}^{+})</math>. Элемент матрицы <math>p_{ij}</math> — время обслуживания требования <math>i</math> на машине <math>j</math>.
Обычно рассматривают следующие целевые функции:
- <math>C_{max}</math>, время окончания обслуживания последнего требования на <math>m</math>-ой машине или общее время обслуживания;
- <math>\Sigma^{n}_{i=1} c_i</math>, сумму времен окончания обслуживания требований на машине <math>m</math>.
Алгоритмы минимизации <math>C_{max}</math>
Алгоритм для двух машин
Для решения задачи на двух машинах найден полиномиальный по времени алгоритм Джонсона[2]: требования разделяются на два множества <math>U = \{i : p_{i1} < p_{i2}\}</math> и <math>V = \{i : p_{i1} \geq p_{i2}\}</math>, далее:
- требования <math>U</math> упорядочиваются по неубыванию <math>p_{i1}</math>,
- требования <math>V</math> упорядочиваются по невозрастанию <math>p_{i2}</math>,
- оптимальная последовательность является конкатенацией упорядоченных таким образом <math>U</math> и <math>V</math>.
Алгоритм имеет временную сложность <math>n \log(n)</math>, поскольку использует алгоритм сортировки.
Алгоритмы для трёх и более машин
В случае более двух машин эта задача является NP-трудной, но разработано множество эвристических полиномиальных по времени приближённых алгоритмов[3].
Эвристика NEH
Одним из наиболее известных алгоритмов является эвристика Наваза, Энскора и Хама (Nawaz, Enscore, Ham)[4]:
- требования упорядочиваются по <math> \sum_{j=1}^{m} p_{ij} </math> и нумерюутся в соответствии с этим порядком,
- определяется порядок обслуживания двух первых требований так, чтобы минимизировать время их обслуживания,
- для <math>i = 3</math> до <math>n</math>:
- помещается требование <math>i</math> на позицию <math>k \in [1,i]</math>, которая минимизирует общее время обслуживания первых <math> i </math> требований
- (конец цикла)
Эвристика Кэмпбелла, Дудека и Смита
Известна также эвристика Кэмпбелла, Дудека и Смита (Campbell, Dudek, Smith), в которой задача для <math>m</math> машин последовательно сводится к <math>m-1</math> задаче для 2 машин[5] и каждая из них решается алгоритмом Джонсона.
Примечания
- ↑ Шаблон:Cite web
- ↑ S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.
- ↑ A comprehensive review and evaluation of permutation flowshop heuristics
- ↑ [1] A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
- ↑ Шаблон:Cite web
