Том 7, серия 1, номер 4, 2000 г., Стр. 59-77

УДК 519.854
К. Н. Каширских, С. В. Севастьянов, И. Д. Черных
Четырёхпараметрический анализ сложности задачи 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.

Каширских К. Н. ¹
Севастьянов С. В. ¹
Черных И. Д. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 27 апреля 2000 г.