Полиномиально разрешимый случай двухстадийной задачи Open Shop с тремя машинами

Авторы: Каширских К.Н., Кононов А.В., Севастьянов С.В., Черных И.Д.
Журнал: Дискретный анализ и исследование операций
Том: 8
Номер: 1
Год издания: 2001
Издательство: Изд-во Ин-та математики
Местоположение издательства: Новосибирск
Первая страница: 24
Последняя страница: 40
Аннотация: Рассматривается двухстадийная задача open shop на трех машинах с критерием «минимум длины расписания». Вопрос о сложности этой задачи, поставленный Гонзалезом и Са́ни в 1976 г., до сих пор остается открытым. В статье доказывается, что задача полиномиально разрешима при Lmax⩾3pmax, где Lmax –максимальная машинная нагрузка, pmax – максимальная длительность операции. При этом длина оптимального расписания равняется Lmax.
Добавил в систему: Кононов Александр Вениаминович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ПсковГУ
	Главная Поиск Статистика О проекте Помощь

ИСТИНА