Россия
Россия
В статье рассматриваются специфические случаи решения задач упаковки/укладки геометрических объектов, характерные для подотраслей деревообработки. Унифицированные математические модели и реализованные на их основе алгоритмы составляют математическое обеспечение систем автоматизированного проектирования (САПР) соответствующих производств.
Геометрическое моделирование, оптимизация, укладка, упаковка, размещение объектов
I. Введение
Решение задачи упаковки/укладки геометрических объектов с необходимостью востребовано во многих отраслях производства. Она относится к разряду NP-трудных комбинаторных задач, для решения которых доказано отсутствие общего алгоритма решения [1].
В общей постановке задача ставится следующим образом: упаковать объекты определенной формы в конечное число контейнеров предопределенной формы таким способом, чтобы число использованных контейнеров было минимальным или количество или объем упакованных объектов были максимальным [2].
Обсудим некоторые частные задачи размещения, возникающие в САПР деревообрабатывающих подотраслей, рассматривая их особенности на примерах унифицированной постановки.
II. Модель задачи оптимизации поставов пиловочных бревен
В лесопильном производстве бревно, как контейнер для упаковки, представляется телом вращения. Форма древесного ствола, зависящая от особенностей породы, возраста и внешних условий роста и развития, может быть описана образующей ствола с той или иной точностью. Рассматривая участки ствола, отграниченные разными по форме кривыми, их с некоторым допущением можно приравнивать к правильным стереометрическим телам вращения: усеченный нейлоид, цилиндр, усеченный параболоид, конус. Таким образом, ствол по форме можно приравнять к сложному телу вращения [3]. Необходимо получить оптимальную схему раскроя бревна на пиломатериалы (постав), соблюдая, с одной стороны, спецификационные требования, с другой стороны, минимум отходов, или максимум заполнения объема. Сформулируем задачу, используя, как специфику технологии лесопильного производства, так и индивидуальный подход к раскрою/упаковке объектов [4].
Проблема оптимизации поставов по максимуму используемой площади сечения бревна (контейнера) является базовой для многих задач технологии лесопиления [5].
1. Пападимитриу, Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х. Пападимитриу, К. Стайглиц. – М. : Мир, 1985. – 512 с.
2. Стоян, Ю. Г. Размещение геометрических объектов / Ю.Г. Стоян. – Киев : Наукова думка, 1975. – 240 с.
3. Фельдман, Х. Л. Система максимальных поставов на распиловку [Текст] / Х. Л. Фельдман. Л. : Гослестехиздат, 1932. – 230 c.
4. Оптимизация раскроя и размерных показателей пиловочника / В.А. Гарин, Е.А. Лимонов, Д.П. Федоров, Е.С. Хухрянская // Деревообрабатывающая промышленность. –1998. – № 1. – С. 11–14.
5. Хухрянская, Е. С. Математические модели раскроя лесоматериалов : автореф. … канд. техн. наук: 05.21.05 / Е. С. Хухрянская. – Воронеж, 1998. – 18 с.
6. Калитеевский, Р.Е. Лесопиление в XXI веке. Технология, оборудование, менеджмент / Р. Е. Калитеевский. – СПб. : ПРОФИ-ИНФОРМ, 2005. – 480 с.
7. Петровский, В. С. Автоматическая оптимизация раскроя древесных стволов / В. С. Петровский. – М. : Лесная промышленность, 1970. – 183 с.
8. Мартынов, В. В. Регулярное размещение двумерных геометрических объектов сложной формы / В. В. Мартынов, А. М. Валиуллин // Прикладная геометрия. – 2001. – Вып. 3, № 4. – С. 9-20.
9. Сарайкин, В. Г. Оптимальный раскрой листовых и плитных материалов / В. Г. Сарайкин, Е. С. Хухрянская // Лесная промышленность, 2003. – №1. – С. 21–27.
10. Авакумов, В. Д. Численное решение задач оптимального размещения плоских объектов / В. Д. Авакумов // Прикладная геометрия. – 2007. – Вып.9, № 19. – С. 13 – 23.
11. Мухачева, А. С. Конструирование алгоритмов локального поиска оптимума прямоугольной упаковки на базе двойственных задач линейного раскроя / А. С. Мухачева, Э. А. Мухачева // Информационные технологии. – 2002. – № 6. – С. 25–30.
12. Хухрянская, Е. С. Унифицированное описание модели входного объекта для САПР паркетных работ / Е. С. Хухрянская, В. Н. Харин, И. С. Кущева // Системы управления и информационные технологии. – 2006. – № 3 – С. 92 – 96.
13. Кущева, И. С. Унифицированное описание модели раппорта регулярной укладки паркета / И. С. Кущева, Е.С. Хухрянская / Математическое моделирование, компьютерная оптимизация технологий, параметров оборудования и систем управления лесного комплекса : сб. науч. трудов. – Воронеж, 2007.– С. 52-56.
14. Кущева, И. С. Модели формирования регулярной укладки из штучного паркета / И. С. Кущева, Е. С. Хухрянская, В. Н. Харин // Природопользование: ресурсы, техническое обеспечение : сб. науч. трудов. – Воронеж, 2007. – С. 86-89.
