Матэвристика на основе локального поиска для одной модификации обобщённой задачи о назначениях

Матэвристика на основе локального поиска для одной модификации обобщённой задачи о назначениях

Захарова Ю. В., Заозёрская Л. А.
Дискретный анализ и исследование операций, 33, 1, 71-90 (2026)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2026.33.842

Аннотация:

Рассматривается новая модификация обобщённой задачи о назначениях с ограничениями на объёмы и типы работ. Заданное множество работ необходимо распределить между агентами (исполнителями). Каждая работа имеет объём и тип. Для каждого агента заданы ограничения на количество типов назначенных работ, общий объём назначенных работ, а также эффективность выполнения работ. Требуется максимизировать суммарную эффективность назначения при заданных ограничениях на загрузку. Исследуется вычислительная сложность задачи. Предлагается алгоритм локального поиска с окрестностями произвольного размера, где учитываются известные подходы к решению обобщённой задачи о назначениях и дополнительные условия рассматриваемой задачи. Окрестности строятся путём частичного фиксирования значений переменных, соответствующих назначению работ. Для решения соответствующих подзадач используются точные алгоритмы из известных пакетов решения задач математического программирования. Экспериментальные результаты показывают, что предложенный алгоритм демонстрирует конкурентоспособные результаты по качеству получаемых решений в сравнении с гибридными алгоритмами на основе методов ветвей и отсечений из известных пакетов Gurobi и SCIP при заданном ограничении времени счёта на серии тестовых примеров с различными структурными свойствами. 

Табл. 7, библиогр. 29.

Литература:
  1. Kundakcioglu O. E., Alizamir S. Generalized assignment problem // Encyclopedia of optimization. Boston, MA: Springer, 2008. P. 1153–1162.
     
  2. Ross G. T., Soland R. M. Modeling facility location problems as generalized assignment problems // Manag. Sci. 1977. V. 24. P. 345–357.
     
  3. Zaozerskaya L. Analysis of integer programming model of academic load distribution // Mathematical Optimization Theory and Operations Research. Rev. Sel. Pap. 18th Int. Conf. (Yekaterinburg, Russia, July 8–12, 2019). Cham: Springer, 2019. P. 266–279. (Commun. Comput. Inf. Sci.; V. 1090). DOI: 10.1007/978-3-030-33394-2_21.
     
  4. Zhang C. W., Ong H. L. An efficient solution to biobjective generalized assignment problem // Adv. Eng. Softw. 2007. V. 38. P. 50–58.
     
  5. Cohen R., Katzir L., Raz D. An efficient approximation for the generalized assignment problem // Inform. Process. Lett. 2006. V. 100, No. 4. P. 162–166.
     
  6. Dawande M., Kalagnanam J. The multiple knapsack problem with color constraints. Yorktown Heights, NY: IBM TJ Watson Res. Center, 1998.
     
  7. Kondakov A., Kochetov Y. A core heuristic and the branch-and-price method for a bin packing problem with a color constraint // Optimization Problems and Their Applications. Rev. Sel. Pap. 7th Int. Conf. (Omsk, Russia, July 8–14, 2018). Cham: Springer, 2018. P. 309–320. (Commun. Comput. Inf. Sci.; V. 871). DOI: 10.1007/978-3-319-93800-4_25.
     
  8. Zaozerskaya L. A., Plankova V. A. Researching and solving a bicriteria supply management problem with the given volumes of batches // J. Phys.: Conf. Ser. 2019. V. 1210. Article ID 012164. 7 p.
     
  9. Ngoo C. M., Goh S. L., Sze S. N., Sabar N. R., Hijazi M. H. A., Kendall G. A survey of mat-heuristics for combinatorial optimisation problems: Variants, trends and opportunities // Appl. Soft Comput. 2024. V. 164. Article ID 111947. 17 p.
     
  10. Заозёрская Л. А., Захарова Ю. В. Модели и алгоритмы локального поиска для маршрутизации транспортных средств с возвратами и временными окнами // Изв. Иркутск. гос. ун-та. Сер. Математика. 2024. Т. 48. C. 95–110.
     
  11. Ibaraki T., Ohashi T., Mine H. A heuristic algorithm for mixed-integer programming problems // Approaches to integer programming. Heidelberg: Springer, 2009. P. 115–136.
     
  12. Berthold T., Heinz S., Pfetsch M. E., Vigerske S. Large neighborhood search beyond MIP. ZIB-Report 11-21. Berlin: Konrad-Zuse-Zentrum Inform., 2011. 12 p.
     
  13. Genova K. A heuristic algorithm for solving mixed integer problems // Cybern. Inf. Technol. 2011. V. 11, No. 2. P. 3–12.
     
  14. Danna E., Rothberg E., Pape C. L. Exploring relaxation induced neighborhoods to improve MIP solutions // Math. Program. 2005. V. 102, No. 1. P. 71–90.
     
  15. Fischetti M., Lodi A. Local branching // Math. Program. 2003. V. 98, No. 1. P. 23–47.
     
  16. Balachandar S. R., Kannan K. A new heuristic approach for the large-scale generalized assignment problem // Int. J. Math. Comput. Phys. Elect. Comput. Eng. 2009. V. 3. P. 969–974.
     
  17. Narciso M. G., Lorena L. A. N. Lagrangian/surrogate relaxation for generalized assignment problems // Eur. J. Oper. Res. 1999. V. 114. P. 165–177.
     
  18. Haddadi S. Lagrangian decomposition based heuristic for the generalized assignment problem // Inf. Syst. Oper. Res. 1999. V. 37, No. 4. P. 392–402.
     
  19. Amini M. M., Racer M. A rigorous computational comparison of alternative solution methods for the generalized assignment problem // Manag. Sci. 1994. V. 40, No. 7. P. 868–890.
     
  20. D7.0az J. A., Fernandez E. A tabu search heuristic for the generalized assignment problem // Eur. J. Oper. Res. 2001. V. 132, No. 1. P. 22–38.
     
  21. Feltl H., Raidl G. R. An improved hybrid genetic algorithm for the generalized assignment problem // Proc. 2004 ACM Symp. Appl. Comput. (Nicosia, Cyprus, Mar. 14–17, 2004). New York: ACM Press, 2004. P. 990–995. 
     
  22. French A. P., Wilson J. M. An LP-based heuristic procedure for the generalized assignment problem with special ordered sets // Comput. Oper. Res. 2007. V. 34, No. 8. P. 2359–2369.
     
  23. Trick M. A. A linear relaxation heuristic for the generalized assignment problem // Nav. Res. Logist. 1992. V. 39, No. 2. P. 137–151.
     
  24. Cattrysse D. G., Salomon M., Van Wassenhove L. N. A set partitioning heuristic for the generalized assignment problem // Eur. J. Oper. Res. 1994. V. 72, No. 1. P. 167–174.
     
  25. Forrest J. J. H., Kalagnanam J., Ladanyi L. A column-generation approach to the multiple knapsack problem with color constraints // INFORMS J. Comput. 2006. V. 18, No. 1. P. 129–134.
     
  26. Srinivasan V., Thompson G. L. An algorithm for assigning uses to sources in a special class of transportation problem // Oper. Res. 1973. V. 21, No. 1. P. 284–295.
     
  27. Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco, CA: Freeman, 1979. 338 p.
     
  28. Munkres J. Algorithms for the assignment and transportation problems // J. Soc. Ind. Appl. Math. 1957. V. 5, No. 1. P. 32–38.
     
  29. Rudolph G. Finite Markov chain results in evolutionary computation: A tour d’horizon // Fund. Inform. 1998. V. 35, No. 1–4. P. 67–89.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2026–0019). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Захарова Юлия Викторовна
  1. Омский филиал Института математики им. С. Л. Соболева, 
    ул. Певцова, 13, 644099 Омск, Россия

E-mail: yzakharova@ofim.oscsbras.ru 

Заозёрская Лидия Анатольевна
  1. Омский филиал Института математики им. С. Л. Соболева, 
    ул. Певцова, 13, 644099 Омск, Россия
  2. Омский гос. технический университет, 
    пр. Мира, 11, 644050 Омск, Россия

E-mail: zaozer@ofim.oscsbras.ru 

Статья поступила 15 октября 2025 г.
После доработки — 12 ноября 2025 г.
Принята к публикации 22 декабря 2025 г.

Abstract:

The paper considers a new modification of the generalized assignment problem with constraints on volumes and types of jobs. A set of jobs must be assigned to a set of agents (performers). Each job has volume and type. For each agent, constraints are defined on the number of assigned job types, the total volume of assigned jobs, and the efficiency of job execution. The objective is to maximize the total assignment efficiency subject to the given loading constraints. The computational complexity is analyzed. We propose a local search algorithm with neighborhoods of variable size which takes into account known approaches for solving the generalized assignment problem and the additional constraints of the considered problem. The neighborhoods are constructed by partially fixing the values of the variables corresponding to the assignment of jobs. Exact algorithms from the well-known mathematical programming problem-solving packages are used to solve the corresponding subproblems. Experimental results show that the proposed algorithm achieves results competitive to the hybrid algorithms based on branch-and-cut methods from Gurobi and SCIP solvers in terms of solution quality under given time limit on a series of test instances with various structural properties. 

Tab. 7, bibliogr. 29.

References:
  1. O. E. Kundakcioglu and S. Alizamir, Generalized assignment problem, in Encyclopedia of Optimization (Springer, Boston, MA, 2008), pp. 1153–1162.
     
  2. G. T. Ross and R. M. Soland, Modeling facility location problems as generalized assignment problems, Manag. Sci. 24, 345–357 (1977).
     
  3. L. Zaozerskaya, Analysis of integer programming model of academic load distribution, in Mathematical Optimization Theory and Operations Research, Rev. Sel. Pap. 18th Int. Conf. (Yekaterinburg, Russia, July 8–12, 2019) (Springer, Cham, 2019), pp. 266–279 (Commun. Comput. Inf. Sci., Vol. 1090), DOI: 10.1007/978-3-030-33394-2_21.
     
  4. C. W. Zhang and H. L. Ong, An efficient solution to biobjective generalized assignment problem, Adv. Eng. Softw. 38, 50–58 (2007).
     
  5. R. Cohen, L. Katzir, and D. Raz, An efficient approximation for the generalized assignment problem, Inform. Process. Lett. 100 (4), 162–166 (2006).
     
  6. M. Dawande and J. Kalagnanam, The Multiple Knapsack Problem with Color Constraints (IBM TJ Watson Res. Center, Yorktown Heights, NY, 1998).
     
  7. A. Kondakov and Y. Kochetov, A core heuristic and the branch-and-price method for a bin packing problem with a color constraint, in Optimization Problems and Their Applications, Rev. Sel. Pap. 7th Int. Conf. (Omsk, Russia, July 8–14, 2018) (Springer, Cham, 2018), pp. 309–320 (Commun. Comput. Inf. Sci., Vol. 871), DOI: 10.1007/978-3-319-93800-4_25.
     
  8. L. A. Zaozerskaya and V. A. Plankova, Researching and solving a bicriteria supply management problem with the given volumes of batches, J. Phys., Conf. Ser. 1210, ID 012164 (2019).
     
  9. C. M. Ngoo, S. L. Goh, S. N. Sze, N. R. Sabar, M. H. A. Hijazi, and G. Kendall, A survey of mat-heuristics for combinatorial optimisation problems: Variants, trends and opportunities, Appl. Soft Comput. 164, ID 111947 (2024).
     
  10. L. A. Zaozerskaya and Yu. V. Zakharova, Models and local search algorithms for vehicle routing with returns and time windows, Izv. Irkutsk. Gos. Univ., Ser. Mat. 48, 95–110 (2024).
     
  11. T. Ibaraki, T. Ohashi, and H. Mine, A heuristic algorithm for mixedinteger programming problems, in Approaches to Integer Programming (Springer, Heidelberg, 2009), pp. 115–136.
     
  12. T. Berthold, S. Heinz, M. E. Pfetsch, and S. Vigerske, Large neighborhood search beyond MIP. ZIB-Report 11-21 (Konrad-Zuse-Zentrum Inform., Berlin, 2011).
     
  13. K. Genova, A heuristic algorithm for solving mixed integer problems, Cybern. Inf. Technol. 11 (2), 3–12 (2011). 
     
  14. E. Danna, E. Rothberg, and C. L. Pape, Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program. 102 (1), 71–90 (2005).
     
  15. M. Fischetti and A. Lodi, Local branching, Math. Program. 98 (1), 23–47 (2003).
     
  16. S. R. Balachandar and K. Kannan, A new heuristic approach for the largescale generalized assignment problem, Int. J. Math. Comput. Phys. Elect. Comput. Eng. 3, 969–974 (2009).
     
  17. M. G. Narciso and L. A. N. Lorena, Lagrangian/surrogate relaxation for generalized assignment problems, Eur. J. Oper. Res. 114, 165–177 (1999).
     
  18. S. Haddadi, Lagrangian decomposition based heuristic for the generalized assignment problem, Inf. Syst. Oper. Res. 37 (4), 392–402 (1999).
     
  19. M. M. Amini and M. Racer, A rigorous computational comparison of alternative solution methods for the generalized assignment problem, Manag. Sci. 40 (7), 868–890 (1994).
     
  20. J. A. D7.0az and E. Fernandez, A tabu search heuristic for the generalized assignment problem, Eur. J. Oper. Res. 132 (1), 22–38 (2001).
     
  21. H. Feltl and G. R. Raidl, An improved hybrid genetic algorithm for the generalized assignment problem, in Proc. 2004 ACM Symp. Appl. Comput. (Nicosia, Cyprus, Mar. 14–17, 2004) (ACM Press, New York, 2004), pp. 990–995.
     
  22. A. P. French and J. M. Wilson, An LP-based heuristic procedure for the generalized assignment problem with special ordered sets, Comput. Oper. Res. 34 (8), 2359–2369 (2007).
     
  23. M. A. Trick, A linear relaxation heuristic for the generalized assignment problem, Nav. Res. Logist. 39 (2), 137–151 (1992).
     
  24. D. G. Cattrysse, M. Salomon, and L. N. Van Wassenhove, A set partitioning heuristic for the generalized assignment problem, Eur. J. Oper. Res. 72 (1), 167–174 (1994).
     
  25. J. J. H. Forrest, J. Kalagnanam, and L. Ladanyi, A column-generation approach to the multiple knapsack problem with color constraints, INFORMS J. Comput. 18 (1), 129–134 (2006).
     
  26. V. Srinivasan, G. L. Thompson, An algorithm for assigning uses to sources in a special class of transportation problem, Oper. Res. 21 (1), 284–295 (1973).
     
  27. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979).
     
  28. J. Munkres, Algorithms for the assignment and transportation problems, J. Soc. Ind. Appl. Math. 5 (1), 32–38 (1957).
     
  29. G. Rudolph, Finite Markov chain results in evolutionary computation: A tour d’horizon, Fund. Inform. 35 (1–4), 67–89 (1998).