-полнота задачи распределения групп задач по группам исполнителей
(Стр. 47-54)
Подробнее об авторах
Игнатьев Юрий Васильевич
аспирант
Московский государственный технический университет имени Н.Э. Баумана
г. Москва, Российская Федерация Афанасьев Геннадий Иванович кандидат технический наук, доцент; доцент; Московский государственный технический университет имени Н.Э. Баумана; г. Москва, Российская Федерация
Московский государственный технический университет имени Н.Э. Баумана
г. Москва, Российская Федерация Афанасьев Геннадий Иванович кандидат технический наук, доцент; доцент; Московский государственный технический университет имени Н.Э. Баумана; г. Москва, Российская Федерация
Нажимая на кнопку купить вы соглашаетесь с условиями договора оферты
Аннотация:
В статье представлено доказательство полиномиального сведения исследуемой задачи теории расписаний о распределении групп задач по группам исполнителей к одной из обобщенных вариаций NP-полной задачи о взвешенном вершинном покрытии. Исходные данные и ограничения исследуемой задачи представлены гипперграфом, с использованием мягких ребер для обхода комбинаторного взрыва в вариациях обработки групп задач. Цели исследования заключались в формальном доказательстве свойства NP-полноты исследуемой задачи; а также, поиске методов и алгоритмов решения схожих задач в смежной с теорией расписаний области математики теории сложности вычислений. В ходе исследования доказано полиномиальное сведение исходных данных и ограничений исследуемой задачи к одной из вариаций задачи о взвешенном вершинном покрытии, схожей с задачей о вершинном покрытии с ограничениями по емкости (Vertex Cover with Hard Capacities, VHCH) на гипперграфе. Которое обходит комбинаторный взрыв вариантов обработки групп задач на группах исполнителей за счет мягких ребер. Установлено, что в области теории сложности вычислений существуют методы и алгоритмы для решения схожих задач, идеи которых возможно применить к решению исследуемой задачи.
Образец цитирования:
ОБРАЗЕЦ ЦИТИРОВАНИЯ: Игнатьев Ю.В., Афанасьев Г.И. NP-полнота задачи распределения групп задач по груп-пам исполнителей // Computational Nanotechnology. 2026. Т. 13. № 1. С. 47-54. DOI: 10.33693/2313-223X-2026-13-1-47-54. EDN: MKWRNG
Список литературы:
Левин Л.А. Универсальные задачи перебора // Проблемы передачи информации. 1973. Т. 9. № 3. С. 115–116.
Cook S.A. The complexity of theorem-proving procedures // Proceedings of the third annual ACM Symposium on Theory of Computing – STOC’71. N.Y., N.Y., USA: ACM Press, 1971. Pp. 151–158.
Garey M.R., Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman (ed.). New York: Bell Telephone Laboratories, Incorporated, 1979. 340 p.
Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling // Mathematics of Operations Research. 1976. Vol. 1. No. 2. Pp. 117–129. DOI: 10.1287/moor.1.2.117.
Guha S. et al. Capacitated vertex covering // Journal of Algorithms. 2003. Vol. 48. No. 1. Pp. 257–270. DOI: 10.1016/S0196-6774(03)00053-1.
Kao M.-J. Iterative partial rounding for vertex cover with hard capacities // Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. Pp. 2638–2653.
Karp R.M. Reducibility among combinatorial problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. (50 years of integer programming 1958–2008)
Khobotov E.N., Ermolova M.A. Formation of work plans and schedules at enterprises with conveyor assembly // IFIP Advances in Information and Communication Technology. 2021. Pp. 572–579.
Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems // Annals of Discrete Mathematics. 1977. Vol. 1. Pp. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.
Nemhauser G.L., Trotter L.E. Vertex packings: Structural properties and algorithms // Math. Program. 1975. Vol. 8. No. 1. Pp. 232–248. DOI: 10.1007/BF01580444.
Vazirani V.V. Approximation algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. 380 p.
Wong S.C. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs // ArXiv Preprint. 2017. 15 p.
Cook S.A. The complexity of theorem-proving procedures // Proceedings of the third annual ACM Symposium on Theory of Computing – STOC’71. N.Y., N.Y., USA: ACM Press, 1971. Pp. 151–158.
Garey M.R., Johnson D.S. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman (ed.). New York: Bell Telephone Laboratories, Incorporated, 1979. 340 p.
Garey M.R., Johnson D.S., Sethi R. The complexity of flowshop and jobshop scheduling // Mathematics of Operations Research. 1976. Vol. 1. No. 2. Pp. 117–129. DOI: 10.1287/moor.1.2.117.
Guha S. et al. Capacitated vertex covering // Journal of Algorithms. 2003. Vol. 48. No. 1. Pp. 257–270. DOI: 10.1016/S0196-6774(03)00053-1.
Kao M.-J. Iterative partial rounding for vertex cover with hard capacities // Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017. Pp. 2638–2653.
Karp R.M. Reducibility among combinatorial problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. (50 years of integer programming 1958–2008)
Khobotov E.N., Ermolova M.A. Formation of work plans and schedules at enterprises with conveyor assembly // IFIP Advances in Information and Communication Technology. 2021. Pp. 572–579.
Lenstra J.K., Rinnooy Kan A.H.G., Brucker P. Complexity of machine scheduling problems // Annals of Discrete Mathematics. 1977. Vol. 1. Pp. 343–362. DOI: 10.1016/S0167-5060(08)70743-X.
Nemhauser G.L., Trotter L.E. Vertex packings: Structural properties and algorithms // Math. Program. 1975. Vol. 8. No. 1. Pp. 232–248. DOI: 10.1007/BF01580444.
Vazirani V.V. Approximation algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. 380 p.
Wong S.C. Tight algorithms for vertex cover with hard capacities on multigraphs and hypergraphs // ArXiv Preprint. 2017. 15 p.
Ключевые слова:
теория расписаний, NP-полнота, вершинное покрытие, взвешенное вершинное покрытие, гиперграфы, комбинаторная оптимизация, краткосрочное планирование, динамическое распределение задач, диспетчеризация, полу-онлайн планирование, расписание машин.
