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

Размер шрифта: 
Исследование эффективности решения при моделировании планов размещения и покрытия
Э. И. Дяминова, А. С. Филиппова

Изменена: 2020-05-29

Аннотация


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

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


эффективность решения; моделирование планов; размещение; покрытие

Литература


1. Норенков И.П. Эвристики и их комбинации в генетических методах дискретной оптимизации / И.П. Норенков // Информационные технологии. – 1999. № 1. – С. 2-7.

2. Канторович, Л. В. Рациональный раскрой промышленных материалов. 3-е издание. / Л. В. Канторович, В. А. Залгаллер. СПб: Невский Диалект, 2012. 304 с.

3. Мухачева, Э.А. Метод последовательного уточнения оценок: алгоритм и численный эксперимент для задачи одномерного раскроя / А.С. Мухачева, Г.Н. Белов // Информационные технологии. Машиностроение. – М., 2000. – №2. – С. 13-18.

4. Schwerin, P. The Bin-Packing Problem: a Problem Generator and Some Numerical Experiments with FFD Packing and MTP / P. Schwerin, G. Wascher // International Transactions in Operational Research. – 1997. – Vol. 4. – P.337-389.

5. Hopper, E. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem / E. Hopper, B. Turton // EJOR 128. – 2001. – P. 34-57

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

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

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

9. Хасанова, Э.И. Проектирование размещения геометрических объектов на многосвязном ортогональном полигоне: дис. … канд. техн. наук: 05.13.12 / Хасанова, Элина Ильдаровна. – Уфа, 2011. – 187 с.

10. Телицкий, С.В. Оптимизация многокритериального геометрического покрытия полигона на основе условных оценок с учетом технологических ограничений: дис. … канд. техн. наук: 05.13.01 / Телицкий, Станислав Владиславович. – Уфа, 2013. - 178 с.

11. Мухачева, А.С. Задача прямоугольной упаковки в полубесконечную полосу: численный эксперимент с безотходными задачами E.Hopper на базе алгоритмов блочной структуры / А.С. Мухачева, Э.А. Мухачева, А.В. Чиглинцев // Информационные технологии. – М.: Новые технологии, 2005. – №7. – С. 23-32.

12.Bortfeld, A. A genetic algorithm for the twodimensional strip packing problem with rectangular pieces / A. Bortfeld // Eur. J. Oper. Res. – 2006. – Vol. 172(3). – P. 814-837.


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