УДК 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.
