SVERTKI KRITERIEV PRI KOMBINIROVANII REShENIY MNOGOKRITERIAL'NOY AKSIAL'NOY ZADAChI O NAZNAChENIYaKh
- Authors: AFRAYMOVICh L.G1, EMELIN M.D1
-
Affiliations:
- Issue: No 8 (2024)
- Pages: 86-98
- Section: Optimization, system analysis, and operations research
- URL: https://journals.rcsi.science/0005-2310/article/view/262916
- DOI: https://doi.org/10.31857/S0005231024080063
- EDN: https://elibrary.ru/WPFNBF
- ID: 262916
Cite item
Abstract
Рассматривается трехиндексная аксиальная задача о назначениях, которая является одной из классических NP-трудных задач. В рамках задачи о назначениях ставится задача комбинирования допустимых решений, представляющая собой задачу о назначениях на множестве решений, которые содержат только компоненты выбранных допустимых решений. Исследуются вопросы комбинирования решений для многокритериальной задачи с различными видами сверток критериев. В общем случае задача комбинирования оказывается NP-трудной. В работе выделяются условия, при которых задача комбинирования полиномиально разрешима.
About the authors
L. G AFRAYMOVICh
Email: levafraimovich@gmail.com
M. D EMELIN
Email: makcum888e@mail.ru
References
- 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.
- Burkard R., Dell’Amico M., Martello S. Assignment problems: revised reprint. PA: SIAM, 2012.
- 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.
- 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.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- 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.
- 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.
- 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.
- Spieksma F., Woeginger G. Geometric three-dimensional assignment problems // Eur. J. Oper. Res. 1996. V. 91. P. 611-618.
- Custic 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.
- Balas E., Saltzman M.J. An Algorithm for the Three-Index Assignment Problem // Oper. Res. 1991. V. 39. No. 1. P. 150-161.
- Natu S., Date K., Nagi R. GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs // Parallel Comput. 2020. V. 97. 102666.
- Huang G., Lim A. A hybrid genetic algorithm for the Three-Index Assignment Problem // Eur. J. Oper. Res. 2006. V. 172. P. 249-257.
- 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.
- Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения трехиндексной планарной проблемы выбора // Журн. вычислит. мат. и мат. физики. 2006. Т. 46. № 2. С. 222-228.
- Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях // Журн. вычислит. мат. и мат. физики. 2007. Т. 47. № 6. С. 1077-1086.
- Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6. Вып. 1. С. 3-33.
- Прилуцкий М.Х. Многокритериальные многоиндексные задачи объемнокалендарного планирования // Известия РАН. Теория и системы управления. 2007. № 1. C. 78-82.
- Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // АиТ. 1996. № 2. С. 24-29.
- Афраймович Л.Г., Емелин М.Д. Комбинирование решений аксиальной задачи о назначениях // АиТ. 2021. № 8. С. 159-168.
- Афраймович Л.Г., Емелин М.Д. Эвристические стратегии комбинирования решений трехиндексной аксиальной задачи о назначениях // АиТ. 2021. № 10. С. 6-12.
- Afraimovich L.G., Emelin M.D. Complexity of Solutions Combination for the Three-Index Axial Assignment Problem // Mathematics. 2022. V. 10. No. 7. 1062.