УДК 519.87
ФРАГМЕНТАРНІ СТРУКТУРИ В ЗАДАЧІ ДВОВИМІРНОГО ПАКУВАННЯ
У НАПІВОБМЕЖЕНУ СМУГУ
Анотація. Розглянуто загальну задачу двовимірного пакування в напівобмежену смугу. Показано, що її можна розглядати як задачу оптимізації на фрагментарній структурі, яка зводиться до задачі комбінаторної оптимізації на множині переставлень. Розглянуто універсальний спосіб представлення плоских фігур та алгоритм їхнього пакування в смугу. Запропоновано спосіб модифікації початкової задачі для досяжності оптимального розв’язку.
Ключові слова: дискретна оптимізація, фрагментарна структура, двовимірне пакування у смугу, еволюційний алгоритм.
ПОВНИЙ ТЕКСТ
Козин Игорь Викторович,
доктор физ.-мат. наук, профессор, профессор кафедры Запорожского национального университета,
ainc00@gmail.com
Батовский Сергей Евгеньевич,
аспирант Запорожского национального университета, maxishko@ukr.net
СПИСОК ЛІТЕРАТУРИ
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва: Мир, 1982. 416 с.
- Glover F., Taillard E., de Werra D. A user’s guide to tabu search. Annals of Operation Research. 1993. Vol. 41, Iss. 1. P. 1–28.
- Holland J.H. Adaptation in natural and artificial systems. Boston, MA: MIT Press, 1992. 288 p.
- Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы. Известия РАН. Теория и системы управления. 1999. № 1. С. 144–160.
- Gonсalves J.F. A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem. European Journal of Operational Research. 2007. Vol. 183, N 3. P. 1212–1229.
- Штовба С.Д. Муравьиные алгоритмы: теория и применение. Программирование. 2005. № 4. С. 1–16.
- Dorigo М. Optimization, learning, and natural algorithms. PhD Thesis, Dipartimento di Elettronica, Politechnico di Milano, Italy, 1992. 140 p.
- Lodi A., Martello S., Monaci M. Two-dimensional packing problems: A survey. European Journal of Operation Research. 2002. Vol. 141, N 2. P. 241–252.
- Jain S., Gea H.C. Two dimensional packing problems using genetic algorithms. Engineering with Computers. 1998. Vol. 14, N 3. P. 206–213.
- Ванидовский В.А., Лебедев О.Б. Двумерная упаковка в полуограниченную полосу на основе моделирования адаптивного поведения муравьиной колонии. Известия ЮФУ. Технические науки. 2014. № 7 (156). С. 34–42.
- Картак В.М. Задача упаковки прямоугольников. Точный алгоритм на базе матричного представления. Вестник УГАТУ. 2007. Т. 9, № 4 (22). С. 104–110.
- Руднев А.С. Вероятностный поиск с запретами для задачи упаковки кругов и прямоугольников в полосу. Дискретный анализ и исследование операций. 2009. Т. 16, № 4. C. 61–86.
- Стоян Ю.Г., Злотник М.В. Размещение кругов и невыпуклых многоугольников с поворотами в прямоугольнике минимальной длины. Доповіді Національної академії наук України. 2007. № 2. С. 37–42.
- Козин И.В., Максишко Н.К., Перепелица В.А. Фрагментарные структуры в задачах дискретной оптимизации. Кибернетика и системный анализ. 2017. Т. 53, № 6. C. 125–131.
- Козин И.В. Эволюционно-фрагментарная модель задачи упаковки пентамино. Дискретный анализ и исследование операций. 2014. Т. 21, № 6. C. 35–50.
- Романова Т.Е., Ступак Е.А., Злотник М.В. Математическая модель и метод решения задачи оптимизации упаковки произвольных двумерных объектов в прямоугольных областях. Доповіді Національної академії наук України. 2009. № 1. С. 48–53.
