|
Дискретный анализ и исследование операций, сер. 1, 2001, том 8, выпуск 1, страницы 23–39
(Mi da213)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Полиномиально разрешимый случай двухстадийной задачи $open shop$ с тремя машинами
К. Н. Каширских, А. В. Кононов, С. В. Севастьянов, И. Д. Черных Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Рассматривается двухстадийная задача open shop на трех машинах с критерием “минимум длины расписания”. Вопрос о сложности этой задачи, поставленный Гонзалезом и Са́ни в 1976 г., до сих пор остается открытым. В статье доказывается, что задача полиномиально разрешима при $L_{\max}\geqslant 3p_{\max}$, где $L_{\max}$ –максимальная машинная нагрузка, $p_{\max}$ – максимальная длительность операции. При этом длина оптимального расписания равняется $L_{\max}$. Библиогр. 7.
Статья поступила: 24.04.2000
Образец цитирования:
К. Н. Каширских, А. В. Кононов, С. В. Севастьянов, И. Д. Черных, “Полиномиально разрешимый случай двухстадийной задачи $open shop$ с тремя машинами”, Дискретн. анализ и исслед. опер., сер. 1, 8:1 (2001), 23–39
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da213 https://www.mathnet.ru/rus/da/v8/s1/i1/p23
|
Статистика просмотров: |
Страница аннотации: | 288 | PDF полного текста: | 141 |
|