WikiSort.ru - Не сортированное

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

Определение

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

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

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

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

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

Алгоритмы минимизации ${\displaystyle C_{max}}$

Примечания