- Код статьи
- 10.31857/S0005231025050056-1
- DOI
- 10.31857/S0005231025050056
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том / Номер выпуска 5
- Страницы
- 81-97
- Аннотация
- Рассматривается двухкритериальная трехиндексная аксиальная задача о назначениях, которая уже в однокритериальном случае является одной из классических NP-трудных задач. Вра мках данной постановки ставится задача комбинирования допустимых решений, представляющая собой задачу о назначениях на множестве решений, которые содержат только компоненты выбранных допустимых решений. Предлагается полиномиальный алгоритм нахождения Парето-оптимальных решений в задаче комбинирования двух допустимых решений. На его основе строится эвристический подход оценки
- Ключевые слова
- аксиальная задача о назначениях многоиндексные задачи многокритериальные задачи Парето-оптимальность комбинирование решений полиномиальная разрешимость NP-трудность
- Дата публикации
- 01.05.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 15
Библиография
- 1. Spieksma F.C.R. Multi Index Assignment Problems. Complexity, Approximation, Applications. P.M. Pardalos, L.S. Pitsoulis (Eds.) / Nonlinear Assignment Problems: Algorithms and Applications. Dordrecht: Kluwer Acad. Publishers, 2000. P. 1–11.
- 2. Burkard R., Dell’Amico M., Martello S. Assignment problems: revised reprint. PA: SIAM, 2012.
- 3. Kuroki Y., Matsui T. An approximation algorithm for multidimensional assignment problems minimizing the sum of squared errors // Discret. Appl. Math. 2009. V. 157. No. 9. P. 2124–2135.
- 4. Poore A.B. Multidimensional Assignment Problems Arising in Multitarget and Multisensor Tracking. P.M. Pardalos, L.S. Pitsoulis (Eds.) / Nonlinear Assignment Problems: Algorithms and Applications. Dordrecht: Kluwer Acad. Publishers, 2000. P. 13–38.
- 5. Zhuang Y., Zhou Y., Hassini E., Yuan Y., Hu X. ВRack retrieval and repositioning optimization problem in robotic mobile fulfillment systems // Transportation Research Part E: Logistics and Transportation Review, 2022. V. 167. P. 102920.
- 6. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- 7. Афраймович Л.Г. Многоиндексные транспортные задачи с 2-вложенной структурой // АиТ. 2013. № 1. С. 116–134.
- 8. Afraimovich L.G. Multiindex Transportation Problems with 2-embedded Structure // Autom. Remote Control. 2013. V. 74. No. 1. P. 90–104.
- 9. Bandelt H.J., Crama Y., Spieksma F.C.R. Approximation algorithms for multidimensional assignment problems with decomposable costs // Discret. Appl. Math. 1994. V. 49. P. 25–50.
- 10. Crama Y., Spieksma F.C.R. Approximation Algorithms for Three-Dimensional Assignment Problems with Triangle Inequalities // Eur. J. Oper. Res. 1992. V. 60. P. 273–279.
- 11. Burkard R.E., Rudolf R., Woeginger G.J. Three-dimensional axial assignment problems with decomposable cost coefficients // Discret Appl. Math. 1996. V. 65. P. 123–139.
- 12. Spieksma F., Woeginger G. Geometric three-dimensional assignment problems // Eur. J. Oper. Res. 1996. V. 91. P. 611–618.
- 13. ´ Custi´c A., Klinz B., Woeginger G.J. Geometric versions of the three-dimensional assignment problem under general norms // Discret. Optim. 2015. V. 18. P. 38–55.
- 14. Balas E., Saltzman M.J. An Algorithm for the Three-Index Assignment Problem // Oper. Res. 1991. V. 39. No. 1. P. 150–161.
- 15. Natu S., Date K., Nagi R. GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs // Parallel Comput. 2020. V. 97. P. 102666.
- 16. Huang G., Lim A. A hybrid genetic algorithm for the Three-Index Assignment Problem // Eur. J.Oper. Res. 2006. V. 172. P. 249–257.
- 17. Kim B.J., Hightower W.L., Hahn P.M., Zhu Y.R., Sun L. Lower bounds for the axial three-index assignment problem // Eur. J.Oper. 2010. V. 202. P. 654–668.
- 18. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях // Журн. вычислит. мат. и мат. физики. 2007. Т. 47. 6. С. 1077–1086.
- 19. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6. Вып. 1. С. 3–33.
- 20. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объемнокалендарного планирования // Известия РАН. Теория и системы управления. 2007. 1. C. 78-82.
- 21. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // АиТ. 1996. № 2. С. 24–29.
- 22. Афраймович Л.Г., Емелин М.Д. Комбинирование решений аксиальной задачи о назначениях // АиТ. 2021. No. 8. С. 159–168.
- 23. Afraimovich L.G., Emelin M.D. Combining solutions of the axial assignment problem // Autom. Remote Control, 2021. V. 82. No. 8. P. 1418–1425.
- 24. Афраймович Л.Г., Емелин М.Д. Эвристические стратегии комбинирования решений трехиндексной аксиальной задачи о назначениях // АиТ. 2021. № 10. С. 6–12.
- 25. Afraimovich L.G., Emelin M.D. Heuristic Strategies for Combining Solutions of the Three-Index Axial Assignment Problem // Autom. Remote Control, 2021. V. 82. No. 10. 1635–1640.
- 26. Afraimovich L.G., Emelin M.D. Complexity of Solutions Combination for the ThreeIndex Axial Assignment Problem // Mathematics 2022. V. 10. No. 7. 1062.
- 27. Афраймович Л.Г., Емелин М.Д. Свертки критериев при комбинировании решений многокритериальной аксиальной задачи о назначениях // АиТ. 2024. № 8. С. 86–98.
- 28. Afraimovich L.G., Emelin M.D. Convolution of criteria of a multicriterial axial assignment problem // Autom. Remote Control, 2024. V. 85. No. 8. P. 809–818.
