Том 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
Севастьянов С. В. 1
Черных И. Д. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 27 апреля 2000 г.
