Задача минимизации общего времени обработки идентичных деталей | Sciact - Система учета научной деятельности ИМ СО РАН

Задача минимизации общего времени обработки идентичных деталей Научная публикация

Журнал

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Вых. Данные

Год: 2024, Том: 64, Страницы: 99-111 Страниц : 13 DOI: 10.17223/20710410/64/8

Ключевые слова

schedule, identical jobs, NP-hardness, pseudopolynomial algorithm, theory of NP-completeness

Авторы

Романова А.А. ¹ , Сервах В.В. ^1,2 , Тавченко В.Ю. ¹

Организации

1	Омский государственный университет им. Ф. М. Достоевского, Омск, Россия
2	Институт математики им. С. Л. Соболева СО РАН

Информация о финансировании (1)

Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».

FWNF-2022-0020

Рассматривается задача минимизации общего времени обработки идентичных деталей со сложным технологическим маршрутом, когда возможно неоднократное поступление деталей на некоторые машины. Исследуются вопросы вычислительной сложности данной задачи, доказана её NP-трудность в обычном смысле. При фиксированном числе деталей доказана псевдополиномиальная разрешимость задачи. Исследуется вопрос использования циклических расписаний при построении приближённых решений.

Романова А.А. , Сервах В.В. , Тавченко В.Ю.
Задача минимизации общего времени обработки идентичных деталей
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. Т.64. С.99-111. DOI: 10.17223/20710410/64/8 WOS РИНЦ OpenAlex

Опубликована в печати:	24 июн. 2024 г.
Опубликована online:	24 июн. 2024 г.

Web of science:	WOS:001320166600009
РИНЦ:	67349995
OpenAlex:	W4403100421

Пока нет цитирований