Конструирование алгоритмов геометрического размещения на основе матричной и уровневой технологий

Анна Сергеевна Филиппова, Юлия Ильясовна Валиахметова, Элина Ильдаровна Дяминова

Аннотация


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

Ключ. слова


многосвязный ортогональный полигон; матричная технология; уровневая технология; комплексная задача геометрического покрытия и раскроя; безотходные задачи

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

PDF

Литература


Мухачева Э. А., Верхотуров М. А., Мартынов В. В. Модели и методы расчета раскроя-упаковки геометрических объектов. Уфа: УГАТУ, 1998. 216 с.

Валиахметова Ю. И., Филиппова А. С. Теория оптимального использования ресурсов Л. В. Канторовича в задачах раскроя-упаковки: обзор и история развития ме-тодов решения // Вестник УГАТУ. 2014, Т. 18, №. 1 (62), с. 186-197.

Канторович Л. В. Рациональные методы рас-кроя металла // Произв.-техн. бюл. НК Боеприпасов СССР. 1942. № 7–8. С. 21-29.

Мухачева Э. А. Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитиче-ский обзор и перспективы развития / Э. А. Мухачева [и др.] // М: Новые технологии. Информационные технологии. 2004. № 5, Приложение. С. 2-17.

Valiahmetova J. I., Hasanova E. I., Filippova A. S. Some approaches to solve a complex problem of Geometrical covering and orthogonal cutting // Вестник УГАТУ. 2013, т. 17, №. 6 (59), с. 88-91.

Кульга К. С., Меньшиков П. В. Оптимизация геометрического покрытия многосвязного ортогонального полигона с граничными препятствиями с учётом конструк-торско-технологических ограничений // Вестник РГТРУ. Рязань: РГТРУ. 2014. №4. (выпуск 50). Часть 2. С. 75-82.

Дяминова Э. И., Филиппова А. С. Технологии конструирования решений в задачах геометрического размещения // Прикладная математика и фундаменталь-ная информатика: ежегодный научный журнал / Под общ. ред. А. В. Зыкиной. – Омск: Изд-во Ом. гос. ун-та, 2016. № 3. С. 134-141.

Филиппова А. С. Блочная технология констру-ирования алгоритмов для решения задач прямоугольной упаковки полубесконечной полосы // Вестник УГАТУ. 2005. Т. 6. №1 (12). С. 106-116.

Adamovicn A., Albano A. Nesting two-dimensional shapes in rectangular modules // Comput. Aeded Design. 1976. № 8 (1), С. 27-33.

Забелин С. Л., Фроловский В. Д. Разработка и исследование моделей, методов и алгоритмов для синтеза и анализа решений задач геометрического покрытия // Вестник СибГУТИ. 2013. № 2, С. 42-53.

Мухачева Э. А., Валиахметова Ю. И., Хасано-ва Э. И., Телицкий С. В. Проектирование размещения ор-тогональных объектов на полигонах с препятствиями // М.: Новые технологии. Информационные технологии. 2010. № 10. С. 16–22.

Филиппова А. С., Дяминова Э.И., Валиахме-това Ю.И. Метод ограниченной декомпозиции для ре-шения комплексной задачи геометрического покрытия и раскроя // М.: Новые технологии. Информационные тех-нологии. 2016. Т. 22. № 3. С. 179–187.

Хасанова (Дяминова) Э. И. Гильотинное раз-мещение контейнеров в полосе: модификация уровневого алгоритма локального поиска // Принятие решений в условиях неопределенности: межвуз. науч. сб. Уфа: УГАТУ, 2009. Вып. 6. С. 155–161.

Телицкий С. В., Валиахметова Ю. И., Хасано-ва Э. И. Гибридный алгоритм на основе последовательного уточнения оценок для задач максимального ортогонального покрытия // Вестник Башкирского университета. – 2012. Т. 17, № 1 (I). – С. 421-425.

Mukhacheva E.A., Belov G.N., Kartak V.M., Mukhacheva A.S. Linear one-dimensional cutting-packing problems: numerical experiments with sequential value cor-rection method (SVC) and a modified branch-and-bound method (MBB) // Pesquisa Operacional. 2000. 20(2). P.153-168.

Мухачева Э. А. , Хасанова Э. И. Гильотинное размещение контейнеров в полосе: комбинирование эв-ристических технологий // М.: Новые технологии. Инфор-мационные технологии, 2009. № 11. С. 8–14.


Ссылки

  • Ссылки не определены.