ОСОБЕННОСТИ МЕТОДА ПОИСКА С ЗАПРЕТАМИ ДЛЯ ЗАДАЧИ УПАКОВКИ

А. Р. Усманова, Ю. И. Валиахметова

Аннотация


Рассматривается задача упаковки предметов в контейнеры, являющаяся NP-полной. Авторы исследуют один из популярных метаэвристических методов - поиск с запретами (Tabu Search, TS). Предлагается использовать математическую модель родственной задачи - задачи расписания для параллельных процессоров. Авторами предложен алгоритм, позволяющий свести процесс получения оптимального решения в задаче упаковки к получению допустимого решения в задаче расписания процессоров. Рассмотрены две окрестности соседних решений полиномиальной сложности. В работе обсуждаются способы построения одной из самых существенных составляющих метода поиска с запретами - списка запретов (Tabu List, TL). Предложена модель с динамической длиной списка. Также предложена оценочная функция, имеющая константную сложность вычисления. Приведены некоторые результаты численного эксперимента, демонстрирующего эффективность предложенных подходов.

Ключевые слова


ПОИСК С ЗАПРЕТАМИ, ЭВРИСТИЧЕСКИЙ АЛГОРИТМ, ОПТИМИЗАЦИЯ, ДВУМЕРНАЯ УПАКОВКА

Полный текст:

PDF

Литература


Боровых Н. И., Красоткина О. В. Применение алгоритма поиска с запретами в задаче автоматизированного составления оптимального штатного расписания // Известия ТулГУ. Технические науки. 2019. Т. 2, № 6. С. 218–227. [ N. I. Borovyh, O. V. Krasotkina, “Application of the search algorithm with prohibitions in the problem of automated compilation of the optimal staffing schedule”, (in Russian), in Izvestiya TulGU. Tehnicheskie nauki, vol. 6, no. 2, pp. 218-227, 2019. ]

Руднев А. С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу // Дискретный анализ и исследование операций. 2018. Т. 16, № 4. C. 61–86. [ A. S. Rudnev, “Probabilistic tabu search for the problem of packing circles and rectangles into a strip”, (in Russian), in Diskretny`j analiz i issledovanie operacij, vol. 16, no. 4, pp.61-86, 2018. ]

Усманова А. Р. Вероятностные жадные эвристики для задачи упаковки в контейнеры // Первая всероссийская научно-практическая конференция по вопросам решения оптимизационных задач в промышленности: cб. докладов Оптим-2001. СПб.Ж ОПТИМ, 2001. С. 141–145. [ A. R. Usmanova, “Probabilistic Heuristics for the container packing problem”, (in Russian), in The First All-Russian Scientific and Practical conference on the optimization problem in industry solution: Collection of reports Optim-2001. St. Petersburg, 2001. ]

Optimizing base station location and configuration in UMTS networks / E. Amaldi, et al. // ORSA Journal on computing. 1989. Vol. 1, No. 3. Part I. Рp. 190-206.

Glover F. Tabu search – part II // ORSA Journal on computing. 1990. Vol. 2, No. 1. Рp. 4-32.

Martello S.,Toth P. Knapsack Problems, Algorithms and Computer Implemetations. England: John Wiley and Sons Ltd., 1990. 296 p.

A Tabu Search Algorithm for Application Placement in Computer Clustering / J. P. Van der Gaast, et al. // Computers & Operations Research. 2014.Vol. 50, No. 1. Рp. 38-46.

Vogt L., Poojari C. A., Beasley J. E. A tabu search algorithm for the single vehicle routing allocation problem // Journal of the Operational Research Society. 2007. Vol. 58, No. 4. Рp. 467-480.




DOI: https://doi.org/10.54708/26585014_2022_42937

Ссылки

  • На текущий момент ссылки отсутствуют.


(c) 2022 А. Р. Усманова, Ю. И. Валиахметова