Сравнение эффективности различных алгоритмов решения комплексной задачи геометрического покрытия и ортогонального раскроя

Р. А. Ахметьянов; Ю. И. Валиахметова

Информационные технологии интеллектуальной поддержки принятия решений, Информационные технологии интеллектуальной поддержки принятия решений 2016

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

Изменена: 2020-04-09

Аннотация

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

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

разработка алгоритмов; эффективность алгоритмов; геометрическое покрытие; ортогональный раскрой

Литература

1. Телицкий С. В. Оптимизация многокритериального геометрического покрытия полигона на основе условных оценок с учетом технологических ограничений. Диссертация на соискание ученой степени кандидата технических наук. УГАТУ, Уфа, 2012

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

3. ВалиахметоваЮ. И. , МухачеваЭ. А. , ФилипповаА. С., ГильмановаН. А., КариповУ. А. “Мультиметодная технология ортогональной упаковки и ее применение в задачах транспортной логистики”.М.: Новые технологии.Приложение к журналу «Информационные технологии», № 12. 2009. 31 с.

4. Картак В.М. “Матричный алгоритм поиска оптимального решения для задачи упаковки прямоугольников в полубесконечную полосу”. М.: Новые технологии. Информационные технологии, 2008, №2. — С. 24–30.

5. Марков В.Н. “База знаний для негильотинного раскроя-упаковки”. М.: Новые технологии. Информационные технологии. 2007. № 4. С.17–23.

6. Валиахметова Ю. И., Григорчук Т. И., Васильева Л. И., Карамова Л. М. “Технологии моделирования алгоритмов ортогонального раскроя-упаковки и геометрического покрытия: сравнение эффективности”. Электронный журнал «Нефтегазовое дело», 2015, №5, С. 424-445.

7. Валиахметова Ю. И. “Мультиметодная технология моделирования ортогональной упаковки”. Монография. Издатель: LAP LAMBERT Academic Publishing GmbH&Co. KG Dudweiler Landstr. 99,66123 Saarbrucken, Germany.

8. Мухачева Э. А., Мухачева А. С., Валеева А. Ф., Картак В. М. “Методы локального поиска в задачах ортогонального раскроя и упаковки: аналитический обзор и перспективы развития”. М.: Новые технологии. Информационные технологии. 2004. № 5. Приложение. С. 2–17.

9. Валиахметова Ю. И., Филиппова А. С. “Теория оптимального использования ресурсов Л. В. Канторовича в работах Уфимской научной школы”. Омский научный вестник. Серия Приборы, машины и технологии. Журнал, 2013 г. №1(117), с. 39-42.

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

11. Телицкий С. В., Валиахметова Ю. И. “Применение систем автоматизированного проектирования карт раскроя в судостроении”. Вестник воронежского государственного технического университета, 2012, Т. 8, №6. С. 38-43.

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