|
Дискретный анализ и исследование операций, 1996, том 3, выпуск 1, страницы 57–74
(Mi da428)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Достаточное условие эффективной разрешимости задачи open shop
С. В. Севастьяновa, И. Д. Черныхb a Институт математики им. С. Л. Соболева СО РАН
b Новосибирский государственный университет
Аннотация:
Рассматривается задача open shop для $m$ машин и $n$ работ с критерием
минимальности длины расписания. Продолжается рассмотрение подкласса задач
с так называемым условием доминирования, когда нагрузка одной машины,
называемой машиной-доминантой, превышает нагрузки остальных машин по
крайней мере на величину $\Delta$. Доказывается, что при $\Delta\geqslant mp_{\max}$, где $p_{\max}$ – максимальная длительность операции, длина оптимального расписания равна нагрузке машины-доминанты, и приводится алгоритм с временной сложностью
$O(nm^2)$ для нахождения такого расписания. Доказана также теорема о том, что
для случая четырех машин с величиной доминирования $\Delta\geqslant (m-1)p_{\max}$ длина оптимального расписания также равна нагрузке машины-доминанты, и такое
расписание может быть найдено за $O(n)$ операций.
Ил. 16, библиогр. 7
Статья поступила: 23.05.1995
Образец цитирования:
С. В. Севастьянов, И. Д. Черных, “Достаточное условие эффективной разрешимости задачи open shop”, Дискретн. анализ и исслед. опер., 3:1 (1996), 57–74
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da428 https://www.mathnet.ru/rus/da/v3/i1/p57
|
Статистика просмотров: |
Страница аннотации: | 390 | PDF полного текста: | 175 | Первая страница: | 1 |
|