Open AccessРозв'язування задачі розміщення прямокутників на напівнескінченній стрічці алгоритмами локального та табуйованого пошуку
Author(s) -
Л. Ф. Гуляницький,
А. В. Дубіна
Publication year - 2021
Publication title -
naukovij vìsnik užgorodsʹkogo unìversitetu. serìâ matematika ì ìnformatika
Language(s) - Ukrainian
Resource type - Journals
eISSN - 2708-9568
pISSN - 2616-7700
DOI - 10.24144/2616-7700.2021.38(1).123-136
Subject(s) - business
В роботі розглянуто алгоритми стандартного локального та табуйованого пошуку для розв'язування задачі розміщення прямокутників на напівнескінченній стрічці. Особливостями задачі є наявність заборонених областей (дірок), які впливають на ефективність роботи алгоритмів. Досліджувана задача має значну теоретичну цінність і важливе прикладне значення. Ця задача належить до задач NP-повних і більшість методів розв’язування є наближеними.Експериментально досліджено ефективність запропонованих алгоритмів для задачі розміщення прямокутників. Визначено рекордні значення цільової функції, дисперсію, довірчі інтервали та час роботи алгоритмів для задач з різними параметрами.