Russian Federation
Russian Federation
V stat'e rassmatrivayutsya specificheskie sluchai resheniya zadach upakovki/ukladki geometricheskih ob'ektov, harakternye dlya podotrasley derevoobrabotki. Unificirovannye matematicheskie modeli i realizovannye na ih osnove algoritmy sostavlyayut matematicheskoe obespechenie sistem avtomatizirovannogo proektirovaniya (SAPR) sootvetstvuyuschih proizvodstv.
Geometricheskoe modelirovanie, optimizaciya, ukladka, upakovka, razmeschenie ob'ektov
I. Введение
Решение задачи упаковки/укладки геометрических объектов с необходимостью востребовано во многих отраслях производства. Она относится к разряду NP-трудных комбинаторных задач, для решения которых доказано отсутствие общего алгоритма решения [1].
В общей постановке задача ставится следующим образом: упаковать объекты определенной формы в конечное число контейнеров предопределенной формы таким способом, чтобы число использованных контейнеров было минимальным или количество или объем упакованных объектов были максимальным [2].
Обсудим некоторые частные задачи размещения, возникающие в САПР деревообрабатывающих подотраслей, рассматривая их особенности на примерах унифицированной постановки.
II. Модель задачи оптимизации поставов пиловочных бревен
В лесопильном производстве бревно, как контейнер для упаковки, представляется телом вращения. Форма древесного ствола, зависящая от особенностей породы, возраста и внешних условий роста и развития, может быть описана образующей ствола с той или иной точностью. Рассматривая участки ствола, отграниченные разными по форме кривыми, их с некоторым допущением можно приравнивать к правильным стереометрическим телам вращения: усеченный нейлоид, цилиндр, усеченный параболоид, конус. Таким образом, ствол по форме можно приравнять к сложному телу вращения [3]. Необходимо получить оптимальную схему раскроя бревна на пиломатериалы (постав), соблюдая, с одной стороны, спецификационные требования, с другой стороны, минимум отходов, или максимум заполнения объема. Сформулируем задачу, используя, как специфику технологии лесопильного производства, так и индивидуальный подход к раскрою/упаковке объектов [4].
Проблема оптимизации поставов по максимуму используемой площади сечения бревна (контейнера) является базовой для многих задач технологии лесопиления [5].
1. Papadimitriu, H. Kombinatornaya optimizaciya. Algoritmy i slozhnost' / H. Papadimitriu, K. Stayglic. – M. : Mir, 1985. – 512 s.
2. Stoyan, Yu. G. Razmeschenie geometricheskih ob'ektov / Yu.G. Stoyan. – Kiev : Naukova dumka, 1975. – 240 s.
3. Fel'dman, H. L. Sistema maksimal'nyh postavov na raspilovku [Tekst] / H. L. Fel'dman. L. : Goslestehizdat, 1932. – 230 c.
4. Optimizaciya raskroya i razmernyh pokazateley pilovochnika / V.A. Garin, E.A. Limonov, D.P. Fedorov, E.S. Huhryanskaya // Derevoobrabatyvayuschaya promyshlennost'. –1998. – № 1. – S. 11–14.
5. Huhryanskaya, E. S. Matematicheskie modeli raskroya lesomaterialov : avtoref. … kand. tehn. nauk: 05.21.05 / E. S. Huhryanskaya. – Voronezh, 1998. – 18 s.
6. Kaliteevskiy, R.E. Lesopilenie v XXI veke. Tehnologiya, oborudovanie, menedzhment / R. E. Kaliteevskiy. – SPb. : PROFI-INFORM, 2005. – 480 s.
7. Petrovskiy, V. S. Avtomaticheskaya optimizaciya raskroya drevesnyh stvolov / V. S. Petrovskiy. – M. : Lesnaya promyshlennost', 1970. – 183 s.
8. Martynov, V. V. Regulyarnoe razmeschenie dvumernyh geometricheskih ob'ektov slozhnoy formy / V. V. Martynov, A. M. Valiullin // Prikladnaya geometriya. – 2001. – Vyp. 3, № 4. – S. 9-20.
9. Saraykin, V. G. Optimal'nyy raskroy listovyh i plitnyh materialov / V. G. Saraykin, E. S. Huhryanskaya // Lesnaya promyshlennost', 2003. – №1. – S. 21–27.
10. Avakumov, V. D. Chislennoe reshenie zadach optimal'nogo razmescheniya ploskih ob'ektov / V. D. Avakumov // Prikladnaya geometriya. – 2007. – Vyp.9, № 19. – S. 13 – 23.
11. Muhacheva, A. S. Konstruirovanie algoritmov lokal'nogo poiska optimuma pryamougol'noy upakovki na baze dvoystvennyh zadach lineynogo raskroya / A. S. Muhacheva, E. A. Muhacheva // Informacionnye tehnologii. – 2002. – № 6. – S. 25–30.
12. Huhryanskaya, E. S. Unificirovannoe opisanie modeli vhodnogo ob'ekta dlya SAPR parketnyh rabot / E. S. Huhryanskaya, V. N. Harin, I. S. Kuscheva // Sistemy upravleniya i informacionnye tehnologii. – 2006. – № 3 – S. 92 – 96.
13. Kuscheva, I. S. Unificirovannoe opisanie modeli rapporta regulyarnoy ukladki parketa / I. S. Kuscheva, E.S. Huhryanskaya / Matematicheskoe modelirovanie, komp'yuternaya optimizaciya tehnologiy, parametrov oborudovaniya i sistem upravleniya lesnogo kompleksa : sb. nauch. trudov. – Voronezh, 2007.– S. 52-56.
14. Kuscheva, I. S. Modeli formirovaniya regulyarnoy ukladki iz shtuchnogo parketa / I. S. Kuscheva, E. S. Huhryanskaya, V. N. Harin // Prirodopol'zovanie: resursy, tehnicheskoe obespechenie : sb. nauch. trudov. – Voronezh, 2007. – S. 86-89.
