SVERTKI KRITERIEV PRI KOMBINIROVANII REShENIY MNOGOKRITERIAL'NOY AKSIAL'NOY ZADAChI O NAZNAChENIYaKh

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

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

About the authors

L. G AFRAYMOVICh

Нижегородский государственный университет

Email: levafraimovich@gmail.com
д-р физ.-мат. наук Нижний Новгород, Россия

M. D EMELIN

Нижегородский государственный университет

Email: makcum888e@mail.ru
Нижний Новгород, Россия

References

  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. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  6. 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.
  7. 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.
  8. 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.
  9. Spieksma F., Woeginger G. Geometric three-dimensional assignment problems // Eur. J. Oper. Res. 1996. V. 91. P. 611-618.
  10. 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.
  11. Balas E., Saltzman M.J. An Algorithm for the Three-Index Assignment Problem // Oper. Res. 1991. V. 39. No. 1. P. 150-161.
  12. Natu S., Date K., Nagi R. GPU-accelerated Lagrangian heuristic for multidimensional assignment problems with decomposable costs // Parallel Comput. 2020. V. 97. 102666.
  13. Huang G., Lim A. A hybrid genetic algorithm for the Three-Index Assignment Problem // Eur. J. Oper. Res. 2006. V. 172. P. 249-257.
  14. 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.
  15. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения трехиндексной планарной проблемы выбора // Журн. вычислит. мат. и мат. физики. 2006. Т. 46. № 2. С. 222-228.
  16. Дичковская С.А., Кравцов М.К. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях // Журн. вычислит. мат. и мат. физики. 2007. Т. 47. № 6. С. 1077-1086.
  17. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6. Вып. 1. С. 3-33.
  18. Прилуцкий М.Х. Многокритериальные многоиндексные задачи объемнокалендарного планирования // Известия РАН. Теория и системы управления. 2007. № 1. C. 78-82.
  19. Прилуцкий М.Х. Многокритериальное распределение однородного ресурса в иерархических системах // АиТ. 1996. № 2. С. 24-29.
  20. Афраймович Л.Г., Емелин М.Д. Комбинирование решений аксиальной задачи о назначениях // АиТ. 2021. № 8. С. 159-168.
  21. Афраймович Л.Г., Емелин М.Д. Эвристические стратегии комбинирования решений трехиндексной аксиальной задачи о назначениях // АиТ. 2021. № 10. С. 6-12.
  22. Afraimovich L.G., Emelin M.D. Complexity of Solutions Combination for the Three-Index Axial Assignment Problem // Mathematics. 2022. V. 10. No. 7. 1062.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 The Russian Academy of Sciences