Четырехпараметрический анализ сложности задачи open shop

Рассматривается задача open shop на минимум длины расписания. Предлагается сложностной анализ этой задачи в зависимости от значений четырех параметров (числа работ, максимального числа операций работы, числа машин и максимального числа операций на машине), объединяющихся в четырехмерный характеристический вектор $x_I$ заданного входа $I$. Для различных значений четырехмерного вектора $x$ определяются классы $\mathscr I(x)$ индивидуальных задач open shop, характеристический вектор которых не превосходит вектора $x$. Показывается, что в бесконечном множестве нетривиальных классов $\mathscr I(x)$ (допускающих неограниченное общее число операций) существует конечная система так называемых базисных классов, позволяющая определить сложность задачи open shop на классе входов $\mathscr I(x)$ для любого допустимого значения вектора $x$. Табл. 1, ил. 2, библиогр. 7.