Задача минимизации общего времени обработки идентичных деталей Full article
| Journal |
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 64, Pages: 99-111 Pages count : 13 DOI: 10.17223/20710410/64/8 | ||||
| Tags | schedule, identical jobs, NP-hardness, pseudopolynomial algorithm, theory of NP-completeness | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (1)
| 1 | Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН». | FWNF-2022-0020 |
Abstract:
Рассматривается задача минимизации общего времени обработки идентичных деталей со сложным технологическим маршрутом, когда возможно неоднократное поступление деталей на некоторые машины. Исследуются вопросы вычислительной сложности данной задачи, доказана её NP-трудность в обычном смысле. При фиксированном числе деталей доказана псевдополиномиальная разрешимость задачи. Исследуется вопрос использования циклических расписаний при построении приближённых решений.
Cite:
Романова А.А.
, Сервах В.В.
, Тавченко В.Ю.
Задача минимизации общего времени обработки идентичных деталей
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. Т.64. С.99-111. DOI: 10.17223/20710410/64/8 WOS РИНЦ OpenAlex
Задача минимизации общего времени обработки идентичных деталей
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. Т.64. С.99-111. DOI: 10.17223/20710410/64/8 WOS РИНЦ OpenAlex
Dates:
| Published print: | Jun 24, 2024 |
| Published online: | Jun 24, 2024 |
Identifiers:
| Web of science: | WOS:001320166600009 |
| Elibrary: | 67349995 |
| OpenAlex: | W4403100421 |
Citing:
Пока нет цитирований