Том 8, серия 1, номер 1, 2001 г., Стр. 23-39
УДК 519.854
К. Н. Каширских, А. В. Кононов, С. В. Севастьянов, И. Д. Черных
Полиномиально разрешимый случай двухстадийной задачи Open Shop с тремя машинами
Аннотация:
Рассматривается двухстадийная задача open shop на трех машинах с критерием «минимум длины расписания». Вопрос о сложности этой задачи, поставленный Гонзалезом и Са́ни в 1976 г., до сих пор остается открытым. В статье доказывается, что задача полиномиально разрешима при$L_{\max}\geqslant 3p_{\max}$ , где$L_{\max}$ –максимальная машинная нагрузка,$p_{\max}$ – максимальная длительность операции. При этом длина оптимального расписания равняется$L_{\max}$ .
Библиогр. 7.
Каширских К. Н. 1
Кононов А. В. 1
Севастьянов С. В. 1
Черных И. Д. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 24 апреля 2000 г.
