Системний аналіз та методи комбінаторної оптимізації технологічного процесу розкрою

Размещено на http://www.allbest.ru/

Національний університет "Львівська політехніка"

УДК [514.174.2+519.16+519.852]:621.7.01

СИСТЕМНИЙ АНАЛІЗ ТА МЕТОДИ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ТЕХНОЛОГІЧНОГО ПРОЦЕСУ РОЗКРОЮ

01.05.04 - системний аналіз і теорія оптимальних рішень

Автореферат

дисертації на здобуття наукового ступеня

доктора технічних наук

ГРИЦЮК Юрій Іванович

Львів - 2009

Дисертацією є рукопис.

Робота виконана в Національному лісотехнічному університеті України на кафедрі обчислювальної техніки і моделювання технологічних процесів Міністерства освіти і науки України

Науковий консультант: доктор технічних наук, професор, Заслужений діяч науки і техніки України ДУДЮК Дмитро Лук'янович, Національний лісотехнічний університет України

Офіційні опоненти: доктор технічних наук, старший науковий співробітник ГУЛЯНИЦЬКИЙ Леонід Федорович, провідний науковий співробітник відділу методів дискретної оптимізації, математичного моделювання та аналізу складних систем Інституту кібернетики імені В.М. Глушкова Національної академії наук України, м. Київ;

доктор фіз.-мат. наук, професор ЄМЕЦЬ Олег Олексійович, завідувач кафедри математичного моделювання та соціальної інформатики Полтавського університету споживчої кооперації України Укоопспілки та Міністерства освіти і науки України, м. Полтава;

доктор технічних наук, доцент РОМАНИШИН Юрія Михайловича, професор кафедри електронних засобів інформаційно-комп'ютерних технологій Національного університету "Львівська політехніка" Міністерства освіти і науки України, м. Львів.

Захист дисертації відбудеться "_7_"__квітня_2009 р. о "_15_" годині на засіданні спеціалізованої вченої ради Д35.052.14 при Національному університеті "Львівська політехніка" (79013, м. Львів-13, вул. С. Бандери, 28а, ауд. 807, V навч. корпусу).

З дисертацією можна ознайомитися в бібліотеці Національного університету "Львівська політехніка" (79013, м. Львів-13, вул. Професорська)

Автореферат розіслано "_2_"_березня_2009 р.

Вчений секретар

спеціалізованої вченої ради А.Є. Батюк



АНОТАЦІЇ

Грицюк Ю. І. Системний аналіз та методи комбінаторної оптимізації технологічного процесу розкрою. - Рукопис.

Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 01.05.04 системний аналіз і теорія оптимальних рішень. - Національний університет "Львівська політехніка", Львів, 2009.

У роботі вирішено важливу науково-прикладну проблему, пов'язану з оптимізацією технологічного процесу розкрою, результати системного аналізу якого дають змогу визначити принципову можливість його реалізації за наявних або апробованих нових технологій промислового виробництва.

У дисертаційній роботі вперше розроблено наукові основи оптимізації ТП розкрою плитних деревних матеріалів, комплексна математична модель та обчислювальні методи якої забезпечують отримання достовірної інформації про умови його функціонування та своєчасне передбачення змін, а також вироблення стратегій дій для керування ним. Розвинуто теорію і практику оптимізації багатокритеріального плану розкрою, у якій за допомогою технологічних і конструктивних обмежень відображено особливості роботи різних видів виробництв (від масових до індивідуальних), а програмна її реалізація дає змогу за реальний проміжок часу і з достатньою точністю отримати локальний оптимальний розв'язок задачі, придатний для прийняття управлінського рішення. Розроблено методологію моделювання допустимих карт розкрою, математичні моделі та комбінаторні методи генерування яких враховують відомі концептуальні схеми та відповідні їм базові конфігурації карт розкрою, а також дають змогу шляхом внесення комбінованих заготовок їх удосконалювати, або за рахунок різних комбінацій утворювати нові їх конфігурації прогнозованої складності. Удосконалено методику розрахунку ефективності впровадження спроектованого ТП розкрою, яка дає змогу в статиці та динаміці визначити показники його технологічної та економічної ефективності, а також здійснювати інженерно-економічне обґрунтування управлінського рішення про вибір найкращого варіанту з множини допустимих.

Ключові слова: системний аналіз, технологічний процес розкрою, задача розкрою і пакування, моделювання карт розкрою, оптимізація плану розкрою, методи комбінаторної оптимізації, прийняття оптимальних управлінських рішень.



Грыцюк Ю.И. Системный анализ и методы комбинаторной оптимизации технологического процесса раскроя. - Рукопись.

Диссертация на соискание ученой степени доктора технических наук по специальности 01.05.04 системный анализ и теория оптимальных решений. - Национальный университет "Львовская политехника", Львов, 2009. розкрой деревний математичний

В работе решено важную научно-прикладную проблему оптимизации технологического процесса (ТП) раскроя, результаты системного анализа которого позволяют определить принципиальную возможность его реализации при имеющихся или апробированных новых технологиях промышленного производства.

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

Ключевые слова: системный анализ, технологический процесс раскроя, задача раскроя и упаковки, моделирование карт раскроя, оптимизация плана раскроя, методы комбинаторной оптимизации, принятия оптимальных управленческих решений.



Gryciuk Yu. I. System analysis and methods of combinatorial optimization for technological process of cutting. - Manuscript.

Theses on scientific degree of a doctor of engineering sciences on specialty 01.05.04 system analysis and theory of optimal decisions. - Lviv Polytechnic National |University, Lviv, 2009.

Here the important scientific and applied problem is solved linked to optimization of technological process (TP) of cutting for which the results of system analysis enable determining the possibility itself to implement this process under the actual or newly approved technologies of industrial production.

For the first time the scientific foundation for TP optimization of cutting the platen wooden materials are developed in thesis. The obtained complex mathematical model and computational methods yield trustworthy information on functioning conditions and timely foreseeing of TP changes as well as elaborating the strategy for its controlling. The theory and practice is developed for optimization of polycriterial cutting plan where by means of technological and designe limitations the functioning features are displayed for different kinds of productions (from mass to individual ones). Corresponding software enables obtaining suboptimal solution of the task for acceptable time and precision that is good enough for making the managerial decision. The technique is developed for modelling the acceptable cutting maps, thus mathematical models and combinatorial methods for their generation take into account known conceptual schemes and corresponding basic configurations of cutting maps as well as make possible their improvement by introducing combined blanks or create their new configurations of predicted complexity through different combinations. The technique for evaluating the efficiency of implementing the newly designed cutting TP is improved and gives the opportunity to determine indicators of its technological and economic efficiency in static and dynamic modes as well as to make the engineering and economic substantiation for managerial decision when choosing the best option from a multitude of possible ones.

Keywords: system analysis, technological process of cutting, the problem of cutting and packing, modelling the cutting maps, optimization of cutting plan, methods of combinatorial optimization, making the optimal managerial decisions.



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. За останні декілька десятиліть різко зросла кількість проблем, для вивчення та розв'язання яких використовується методологія, теорія та практика системного аналізу з подальшим техніко-економічним обґрунтуванням прийнятих рішень. Цим пояснюється актуальність розвитку наявних і розроблення нових методів прийняття системних рішень, а також принципів побудови і умов функціонування програмних засобів для оптимізації та керування складними ієрархічними системами. Серед науково-прикладних проблем системного аналізу і теорії прийняття рішень одне з чільних місць займає оптимізація технологічного процесу (ТП) розкрою. Основний зміст такої оптимізації полягає в отриманні достовірної інформації про умови функціонування ТП розкрою та своєчасному передбаченні змін, у його об'єктивному прогнозуванні з врахуванням багатофакторних ризиків, у аналізі та синтезі скінченної множини альтернатив можливих розв'язків, а також визначенні стратегій дій для керування ним.

У створення теорії системного аналізу та системної методології проведення досліджень вагомий внесок зробили вчені різних країн - К. Баулдінг, Дж. Клір, М. Месарович, Т. Сааті, Г. Саймон, М.З. Згуровський. Фундаментальним дослідженням методів оптимізації присвячені роботи: академіків НАН України B.C. Михалевича, І.В. Сергієнка, Н.З. Шора, В.Л. Рвачова, Б.Н. Пшеничного, Ю.М. Єрмольєва та ін.; член-кореспондентів НАН України Б.Н. Бублика, К.Л. Ющенко, Ю.Г. Стояна, О.Л. Перевозчикової, В.В. Скопецького, А.Ф. Верланя та ін.

Значний внесок у створення теорії розкрою належить: вітчизняним ученим Л.В. Канторовичу, В.А. Залгаллеру і І.В. Романовському; американським вченим Т. Купмансу, Дж. Данцігу, П. Гілмору і Р. Гоморі; європейським вченим Г. Дикгофу, Г. Вашеру, Ю. Лірову, E.E. Бішофу, С. Марчелу та ін. У машинобудуванні проблемі розкрою належать дослідження Л.Б. Белякової, В.Я. Тимошенка, Ф.В. Бабаєва, А.Б. Опанасюка, А.К. Пандорина, Н.В. Письменчука, В.К. Партаса. Системним аналізом у даній області знань займаються наукові школи, засновниками яких є Е.А. Мухачова і Ю.Г. Стоян. У деревообробному виробництві чимало системних досліджень, пов'язаних з оптимізацією ТП розкрою, проведено під керівництвом М.Н. Феллера, A.A. Піжуріна, В.С. Петровського, І.В. Соболєва, Р.Е. Калітєєвського, І.С. Межова, Т.А. Носовського, Д.Л. Дудюка та ін.

Проте попередні дослідження проблеми розкрою промислових матеріалів спочатку були спрямовані на розроблення досконалих методів оптимізації планів розкрою. З розвитком комп'ютерної техніки прикладалися чималі зусилля до розроблення ефективних методів моделювання допустимих карт розкрою. Пов'язано це з тим, що раніше розкрій плитних матеріалів здійснювався на серійних і масових виробництвах, переважно на одному основному обладнанні за простими картами для одного типорозміру плит і невеликої кількості уніфікованих розмірів заготовок, тобто, тоді як такого ТП розкрою не існувало. За умов індивідуального та дрібносерійного виготовлення продукції, коли практично не діють стандарти на розміри заготовок та використовується значна кількість типорозмірів плит, досягнути високої ефективності процесу розкрою практично неможливо тільки на одному основному обладнанні. Виходом з цієї ситуації є застосування основного і узгодженого за продуктивністю допоміжного обладнання, які разом можуть здійснювати розкрій плит за будь-якими складними картами. У цьому випадку якраз і виникає проблема оптимізації ТП розкрою - структурної оптимізації видів і кількості розкрійного обладнання, параметричної оптимізації їх технічних характеристик. Основою цієї проблеми є моделювання карт і оптимізація плану розкрою.

Отримані раніше дослідниками системні теоретичні та практичні результати вирішення проблеми розкрою як у машинобудівній, так і у деревообробній галузях, а також практичний досвід виробників обладнання свідчать про деякі резерви удосконалення ТП розкрою як складної виробничої системи. Попередніми науковцями виділено основні особливості процесу розкрою плит на заготовки, дана йому детальна характеристика, окреслена множина технологічних і конструктивних обмежень, розроблено чималу кількість обчислювальних методів та алгоритмів. Проте значна низка питань, які стосуються загальної задачі системного аналізу ТП розкрою, зокрема, задачі його структурно-функціонального аналізу, задачі аналізу умов його функціонування, а також задачі його техніко-економічного аналізу не мають достатньої теоретичної та практичної бази: обґрунтованих змістовних формулювань, їх формальних математичних моделей, ефективних методів оптимізації та алгоритмів програмної реалізації. Окрім того, відсутня методологія проектування ТП розкрою з використанням основного і допоміжного обладнання для різних видів виробництв, а також немає рекомендацій щодо використання придатних методів його структурної та параметричної оптимізації.

Тому подальший розвиток методології дослідження ТП розкрою, удосконалення теорії та практики його системного аналізу - розроблення адекватних математичних моделей і ефективних методів його комбінаторної оптимізації для різних видів виробництв (від масових до індивідуальних) та створення на їх базі стратегій проведення виробничих, виробничо-проектних і проектних інженерно-економічних розрахунків для прийняття управлінських рішень є актуальною проблемою. Успішне її вирішення дасть змогу знизити витрати матеріальних і виробничих ресурсів, підвищити продуктивність роботи розкрійного обладнання чи потужність дільниці розкрою, зменшити технологічну собівартість процесу виготовлення продукції, значно покращити якість прийнятих управлінських рішень.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана у рамках планових науково-дослідних робіт з пріоритетних напрямків розвитку науки і техніки згідно з програмою Державного комітету України з питань науки і технологій 05 "Новітні технології та ресурсозберігаючі технології в енергетиці, промисловості та агропромисловому комплексі", 2001-2008 рр. Робота є складовою частиною науково-дослідних робіт, які виконувались і виконуються відповідно до основних напрямків наукової діяльності Національного лісотехнічного університету України "Розробка енерго- і ресурсоекономних технологій і обладнання лісопромислового комплексу України" (розроблено концепцію впровадження матеріало- та ресурсоощадних технологій у деревообробне виробництво). Здобувач як відповідальний виконавець бере участь у науково-дослідній роботі кафедри обчислювальної техніки та моделювання технологічних процесів НЛТУ України: "Комп'ютерно-інформаційні технології підвищення ефективності оброблення деревини", державний реєстраційний № 0104U00 2116, 2004-2006 рр. (розроблено методи моделювання допустимих карт розкрою плит на заготовки різної складності); "Розвиток інформаційних технологій проектування енергозберігаючих процесів оброблення деревини", державний реєстраційний № 0106U012595, 2007-2009 рр. (розроблено методологію проектування оптимальних ТП розкрою плитних матеріалів на заготовки для різних видів виробництв).

Мета і задачі дослідження. Мета роботи полягає в удосконаленні теорії та практики системного аналізу ТП розкрою, розробленні, обґрунтуванні та апробації нових математичних моделей і методів комбінаторної його оптимізації, які забезпечують виконання комплексу інженерно-економічних розрахунків і прийняття управлінських рішень у короткі терміни та з достатньою точністю.

Для досягнення поставленої мети необхідно розв'язати такі основні задачі:

проведення структурно-функціонального аналізу ТП розкрою, формалізований опис складної ієрархічної структури якого дасть змогу за заданими вимогами до нього з'ясувати можливість його реалізації за наявних чи апробованих нових технологій промислового виробництва;

розроблення комбінаторних методів 2D пакування прямокутних об'єктів у межах прямокутної площини відповідно до сучасних виробничих умов формування допустимих карт розкрою плитних деревних матеріалів на заготовки;

розроблення методології моделювання допустимих карт розкрою, математичні моделі яких мають враховувати не тільки відомі концептуальні схеми розкрою та відповідні їм різні за складністю базові конфігурації, але й повинні забезпечити можливість їх удосконалення;

розроблення методу комбінаторної оптимізації плану розкрою промислових плитоформатних матеріалів на заготовки, який забезпечує збіжність процесу розв'язання задачі, цілочисельність отриманого розв'язку та точне виконання запланованої кількості заготовок;

розвиток методології багатоцільової оптимізації плану розкрою, математичні моделі та обчислювальні методи якої мають повною мірою відображати умови функціонування масових і серійних виробництв, а також враховувати особливості роботи сучасних дрібносерійних та індивідуальних деревообробних підприємств;

розроблення теорії та практики проектування ТП розкрою прогнозованої продуктивності згідно з потребами сучасних деревообробних підприємств, адекватні математичні моделі якої мають забезпечити структурну та параметричну його оптимізацію, а також проведення виробничих, виробничо-проектних і проектних розрахунків для прийняття управлінських рішень.

Об'єктом дослідження є ТП розкрою промислових деревних матеріалів, складна ієрархічна структура якого характеризується невизначеністю, неповнотою, неточністю та суперечливістю вхідної інформації.

Предметом дослідження є математичні моделі та методи комбінаторної оптимізації ТП розкрою, які використовуються у різноманітних формалізованих описах задач з достатньою трудомісткістю обчислювальних процедур їх розв'язання, а також забезпечують підтримку рішень під час управління ним.

Методи дослідження ґрунтуються на використанні теорії та практики системного аналізу складних ієрархічних систем, методів математичного моделювання і оптимального проектування, числових методів і засобів комп'ютерної техніки залежно від рівня значущості досліджуваної системи і ступеня повноти початкової інформації про передбачувані умови її функціонування, а також деталізації опису рівнів системи та її функціональних елементів.

Під час аналізу допустимих карт розкрою і синтезу оптимального плану і ТП розкрою як складної виробничої системи використовується методологія, основна мета якої полягає у зменшенні кількості інтерактивних етапів дослідження, базується на положеннях загальної теорії багаторівневих ієрархічних систем, дискретної математики (математичної логіки і теорії алгоритмів), автоматизації виробничих процесів, теорії прийняття рішень, теорії інформації та ін.

Наукова новизна отриманих результатів. Розв'язана науково-прикладна проблема системного аналізу ТП розкрою як складної ієрархічної системи, розроблені математичні моделі та методи комбінаторної оптимізації якого уможливлюють виконання виробничих, виробничо-проектних і проектних інженерно-економічних розрахунків з врахуванням невизначеності, неповноти та суперечливості вхідної інформації. При цьому новими є такі результати:

розвинуто теорію та практику системного аналізу ТП розкрою, формалізовані постановки задач якого дають змогу отримати достовірну інформацію про умови його функціонування та своєчасне передбачення змін, об'єктивне прогнозування з врахуванням багатофакторних ризиків, аналізу та синтезу альтернатив можливих розв'язків, а також вироблення стратегій дій для керування ним;

розвинуто наукові підходи до оптимізації ТП розкрою плитних деревних матеріалів, математичні моделі та обчислювальні методи яких відображають сучасні умови функціонування різних виробництв, дають змогу отримати і дослідити локальні розв'язки комбінаторних задач в умовах невизначеності вхідної інформації;

вперше розроблено метод поетапної комбінаторної оптимізації плану розкрою, який одночасно з генеруванням допустимих карт дає змогу формувати придатний для подальшого використання план розкрою, при цьому виконується умова цілочисельності розв'язку задачі та обмеження на точне виконання запланованої кількості заготовок;

розроблено багатоцільові економіко-математичні моделі розрахунку плану розкрою, критерії оптимізації яких дають змогу визначити вплив технологічних і конструктивних чинників на техніко-економічні показники роботи розкрійного обладнання;

розроблено математичні моделі формування допустимих карт розкрою плитних деревних матеріалів, у яких за допомогою технологічних і конструктивних обмежень враховуються відомі концептуальні схеми та відповідні їм базові конфігурації карт розкрою, а також дають змогу їх удосконалювати;

вперше розроблено метод регулярного послідовно-одиночного двовимірного та багаторівневого розміщування прямокутних об'єктів у межах абстрактної частини прямокутної площини, який дає змогу моделювати карти розкрою прогнозованої складності з урахуванням відповідних обмежень та вимог;

вперше розроблено математичну модель розрахунку тривалості робочого циклу процесу розкрою плит на заготовки за картами різних концептуальних схем і відповідних їм базових конфігурацій, на підставі якої визначаються продуктивність роботи розкрійного обладнання чи потужність дільниці розкрою, а також технологічна собівартість процесу виготовлення заготовок.

Практичне значення одержаних результатів полягає в розробленні нових технологічних рішень щодо моделювання допустимих карт розкрою і проектування матеріало- та ресурсоощадних ТП розкрою.

Практичне значення мають:

програмне забезпечення для моделювання допустимих карт розкрою, концептуальні схеми яких можуть забезпечувати розкрій як всієї плити, її торцевої та основної частин і вкладених карт розкрою, а базові конфігурації можуть складатися з суцільних поздовжньо-поперечних пропилів, або з суцільних поздовжніх, зміщених чи індивідуальних поперечних пропилів, що в сукупності дає змогу значно підвищити ефективність використання розкроюваного матеріалу;

програмне забезпечення для оптимізації багатокритеріального плану розкрою за різними показниками ефективності карт розкрою, спрямованими на збільшення ефективності використання розкроюваного матеріалу, зменшення технологічної собівартості процесу виготовлення заготовок і підвищення продуктивності роботи розкрійного обладнання чи потужності дільниці розкрою;

методика проектування оптимального ТП розкрою заданої продуктивності для довільних типів виробництв (масового, серійного та індивідуального), основою якого є структурна оптимізація кількості пилкових установок з передавальними пристроями і параметрична оптимізація їх технічних характеристик;

програмне забезпечення для розрахунку показників технологічної та економічної ефективності впровадження нового або модернізації наявного ТП розкрою, які дають змогу здійснити техніко-економічне обґрунтування управлінського рішення про вибір найкращого варіанту з множини допустимих.

Реалізація і впровадження результатів роботи. Основні положення і результати дослідження впроваджені: у виробничому відділі ДЛГО "Львівліс" (м. Львів) для проектування та реконструкції дільниць розкрою плитоформатних матеріалів на заготовки; у ДОЗ АТЗТ "Світанок" (м. Львів) для організації технологічних процесів виготовлення віконних і дверних заготовок лінійних і прямокутних форм; у Надвірнянському ЛК (м. Надвірна) для організації технологічних процесів виготовлення меблевих заготовок з ДСП.

Результати дослідження використовуються в навчальному процесі кафедри обчислювальної техніки і моделювання технологічних процесів НЛТУ України з дисциплін "Моделювання та оптимізація процесів деревообробки", "Математичні методи та моделі в розрахунках на ЕОМ ".

Особистий внесок здобувача. Усі наукові результати, викладені у дисертаційній роботі, отримані автором особисто. З наукових праць, опублікованих у співавторстві, здобувачу належить: у роботах [5, 30, 38, 39] - постановка задачі та її математичне формулювання; у роботі [32] - способи відбору множини карт для оптимізації плану розкрою; у роботі [37] - особливості роботи служби головного технолога меблевого виробництва; у роботі [47, 48] - постановка задачі, її математичне формулювання та алгоритм розв'язання.

Апробація результатів дисертації. Основні положення дисертації та окремі її розділи доповідались на: наук.-практ. конф. професорсько-викладацького складу НЛТУ України в період з 1994 до 2008 року; наук.-практ. конф. "Використання персональних ЕОМ в навчальному процесі". - Львів: ЛДУ. - 1994, 8-11 листопада; Міжнародній наук.-практ. конф. "Проблеми автоматизації лісопромислового комплексу". - Львів: УкрДЛТУ, 1996; IX sesja naukowa: Badania dla meblarstwa. - Poznaс, 1996; "State and Development Trends in Wood Industry": 161-164 Stubicke Toplice. Croatia. - 1997; Intercathedra '97: Bulletin of Plant - Economic Department of the European Wood Technology University Studies. - Poznaс. - No 13, 1997; 11 Konferencja Naukowa Wydzialu Technologii Drewna SGGW: Drewno - Material Ekologiczny. - Warszawa, 1997; Международной научно-техн. конф. "Лес - экология и ресурсы". - Минск: БГТУ, 1998; ІІІ-ій Міжнародній школі-семінарі "Теорія прийняття рішень". - Ужгород: УНУ, 2006, 2-7 жовтня; семінарі відділу математичного моделювання і оптимального проектування. - Харків: ІПМаш, 2006, 27 листопада; научно-техн. конф. "Лесной комплекс: состояние и перспективы развития". Брянск. - 2006, 1-3 ноября.

Публікації. Основні положення дисертації опубліковано в трьох індивідуальних монографіях, 38 статтях у наукових фахових виданнях, з них 28 - індивідуальні; 8 доповідей опубліковано в матеріалах наукових конференцій, з них 6 індивідуальні.

Структура і осяг дисертації. Дисертація містить 357 сторінок друкованого тексту, 40 таблиць і 61 рисунок, складається з вступу, шести розділів, висновків, переліку використаних літературних джерел (534 найменувань) і одного додатку. У додатку подано документи і акти про випробування, впровадження і перспективи використання запропонованих розробок.

ЗМІСТ РОБОТИ

У вступі проаналізовано стан наукової проблеми, обґрунтовано актуальність вибраної теми роботи, сформульовано мету і визначено основні задачі дослідження, наведено наукову новизну і практичну значущість отриманих результатів, їх апробацію і практичну реалізацію, а також особистий внесок здобувача.

У першому розділі на базі огляду літературних джерел: наведено особливості системного аналізу ТП розкрою; розглянуто основні передумови розв'язання задачі розкрою промислових матеріалів; проаналізовано запропоновані попередниками шляхи її вирішення; вибрано найбільш перспективні з огляду на сучасні виробничі потреби, можливості математичних моделей і обчислювальних методів; проаналізовано комбінаторні методи розв'язування задач одно- та двовимірного розкрою й пакування; вибрано основні напрямки, які реалізовано першочергово у цьому дослідженні.

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

З'ясовано, що розрахунок плану розкрою з використанням методів ЛП характеризується двома циклами обчислень - моделюванням карт і безпосередньою оптимізацією плану розкрою, значною тривалістю і частою розбіжністю процесу пошуку оптимального його варіанту. Проведені теоретичні та експериментальні оцінки ефективності роботи цих методів свідчать про те, що вони є придатними тільки для розв'язування задач малої та середньої розмірності. Провідні науковці вважають, що у 80- роках ХХ ст. точні методи ЦЛП вийшли на межу своїх можливостей і не варто від них очікувати якісних зрушень у їхніх модифікаціях при збільшенні швидкодії ЕОМ: недоліки мають не технічний, а принциповий характер.

Детальний аналіз сучасного стану комбінаторних методів розв'язання 2D задач розкрою й пакування показав, що більшість дослідників використовують їх релаксацію до задачі меншої розмірності. Побудовані математичні моделі не завжди є адекватними досліджуваному процесу і не відображають важливих особливостей задач у початковій їх постановці. Отримані розв'язки таких задач загалом не є оптимальними, здебільшого допустимими. У найбільш анонсованих роботах, у яких розміщувані об'єкти і області розміщення мають форму прямокутника, як правило, використовують евристичні методи, які навіть в двовимірному випадку не мають адекватних математичних моделей і ефективних методів оптимізації.

У другому розділі проведено аналіз сучасного стану проблеми оптимізації ТП розкрою: з'ясовано причини її виникнення; проаналізовано методи розв'язування багатоекстремальних задач розміщення прямокутних об'єктів; виявлено основні тенденції системного удосконалення карт розкрою, а також основні причини введення до них комбінованих заготовок; наведено компонувальні схеми конструкцій сучасного розкрійного обладнання; проаналізовано наявні на сучасних виробництвах ТП розкрою і визначено перспективні напрямки їх системного удосконалення; на теоретичному рівні дано обґрунтування оптимальності використання плит як сировини.

З'ясовано, що з появою індивідуальних і дрібносерійних виробництв, коли практично не діють стандарти на розміри заготовок і при значній кількості типорозмірів плит, досягнути високої ефективності процесу розкрою практично неможливо тільки на одному основному обладнанні. Виходом з цієї ситуації є застосування як основного, так і узгодженого за продуктивністю допоміжного обладнання, які у сукупності можуть здійснювати розкрій плит за картами прогнозованої складності. Тут якраз і появляється проблема проектування ТП розкрою як складної виробничої системи і, як наслідок, виникає проблема управління ним та його оптимізації: структурної оптимізації видів і кількості функціональних елементів, параметричної стосовно його технічних характеристик.

У роботі розроблено новий концептуальний підхід, згідно з яким процедура моделювання допустимих карт і розрахунку оптимального плану розкрою є складовою частиною розширеної процедури проектування оптимального ТП розкрою. Її зміст - щоби на підставі технічного завдання змоделювати різні його варіанти й вибрати з-поміж них найбільш придатний залежно від поставленої мети проектування. Представлення замовнику для погодження множини альтернатив ТП розкрою є передостаннім етапом оптимального його проектування, після чого здійснюється вибір найкращого для детального опрацювання.

Зокрема, нехай деяка множина альтернатив ТП розкрою є підкласом з множини допустимих його варіантів , визначених певними обмеженнями неврахованих чинників. Нехай задано k робочих критеріїв і їх значення p_t[z] () для z-го ТП розкрою. З множини альтернатив можна виділити підмножину кращих варіантів ТП розкрою. Оскільки варіант z , то він належить оптимальній множині Парето , якщо p_t[z] p_t[z'] (), причому для деякого -го робочого критерію виконується така нерівність: . Якщо множину задовольняють визначені умови опуклості та замкнутості, то для кожного знайдуться такі невід'ємні числа ?_t (: ), що для деякого буде досягатися максимум зваженого критерію

. (1)

Припустимо, що знайдено множину кращих варіантів ТП розкрою ? з множини його альтернатив . Перед проектантом у цьому випадку постає питання, як вибрати єдиний варіант ТП розкрою з множини кращих варіантів , які є не порівнювальними або еквівалентними. Якщо ввести новий показник якості системи F, відома його залежність від критеріїв p_t[z] (), то оптимальний варіант ТП розкрою z* можна визначити з такої умови

. (2)

Детальний аналіз наявних методів прийняття рішень показує, що формальними засобами для складних виробничих систем практично неможливо отримати єдиного оптимального розв'язку. У процесі проектування вибір потрібного варіанту ТП розкрою з множини кращих проводиться, виходячи з таких двох стратегій: якщо вимогам технічного завдання задовольняє декілька варіантів, то серед них вибирається найкращий для більш детального опрацювання на етапі ескізного проектування; якщо жодний з варіантів не задовольняє поставленим вимогам замовника, то тут необхідно вибрати одну з двох стратегій подальшої поведінки - внести зміни у технічне завдання чи відмовитися від подальшого проектування.

Встановлено, що з розвитком комп'ютерної техніки зміст процедури оптимізації плану розкрою залишається незмінним, проте значно удосконалюються методи його оптимізації. Зокрема, для серійних підприємств постановка задачі однокритеріальної оптимізації плану розкрою полягає у знаходженні екстремального значення функції мети, яка може характеризувати:

загальний обсяг отриманих відходів, м²

; (3)

загальну вартість використаних плит різних типорозмірів, грн.

; (4)

при обмеженнях на:

отримання запланованої кількості заготовок у заданих межах, шт.

; (5)



витрати плит не більше наявної кількості, шт.

, (6)

за умови невід'ємності та цілочисельності шуканого розв'язку задачі

. (7)

де: M^м, M^з - відповідно кількість типорозмірів плит і розмірів заготовок, шт.;

- кількість змодельованих карт для плит j-го типорозміру, шт.;

- площа плити j-го типорозміру, м²;

- вартість одиниці площі плити j-го типорозміру, грн./м²;

- отримана кількість заготовок і-го розміру під час розкрою плит j-го типорозміру за k-ою картою, шт.;

- площа відходів, які отримано під час розкрою плит j-го типорозміру за k-ою картою, м²;

- невідома кількість плит j-го типорозміру, яка підлягає розкрою за k-ою картою, шт.;

- наявна кількість плит j-го типорозміру, яким забезпечується підприємство для виготовлення заготовок, шт.

Оскільки ефективність очікуваного плану розкрою може оцінюватися декількома критеріями оптимізації, то і задача розкрою має багатокритеріальний (багатоцільовий) характер, яку загалом записують так:

, (8)

при обмеженнях

, (9)

де: F_g - значення g-ої функції мети; і - відповідно матриця коефіцієнтів і стовпець обмежень. Наявність різних критеріїв оптимізації робить задачу розрахунку оптимального плану розкрою не так визначеною, як у однокритеріальному випадку, яка усувається різними методами узгодження їх між собою: на підставі принципу Парето; методом лінійної згортки; методом технічних обмежень та ін.

З'ясовано, що для моделювання допустимих карт розкрою плитоформатних промислових матеріалів найчастіше використовується метод послідовно-одиночного розміщування прямокутних об'єктів на перестановках, який можна подати у вигляді такої ітераційної процедури:

де: - випадкова послідовність номерів розміщення ПО; Т - загальна кількість перестановок номерів ПО; - значення параметрів розміщеного ПО; - значення параметрів розміщуваного ПО; l_i - довжина ПО.

Встановлено, що основний недолік цього методу та його модифікацій полягає в тому, що чергова згенерована карта розміщення ПО за критерієм відбору переважно є гіршою від найкращої з попередніх, позаяк вона генерується випадково. Це призводить до перегляду значної кількості неперспективних карт розміщення ПО з локальними екстремумами, а також повільному наближенню до глобального значення функції мети. Для зупинки на найкращій з них доводиться використовувати критерії припинення обчислювального процесу.

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

На підставі аналізу відомих методик моделювання карт і розрахунку плану розкрою, наявних виробничих структур ТП розкрою плитних деревних матеріалів, а також можливостей розкрійного обладнання виявлено основні тенденції удосконалення концептуальних схем і відповідних їм базових конфігурацій карт розкрою. Доведено, що перехід від розкрою всієї плити до розкрою її торцевої та основної частин з огляду на одиницю площі плити дає змогу збільшити ефективність її використання, зменшити тривалість робочого циклу процесу розкрою, збільшити продуктивність роботи обладнання, зменшити технологічну собівартість процесу виготовлення заготовок.

На підставі системного аналізу виробничої діяльності інженерів-технологів, робота яких пов'язана з проектуванням карт розкрою, власних багаточисленних розрахунків за різними специфікаціями деталей виявлено основні причини, які приводять до застосування так званих комбінованих заготовок, введення їх на однакових або обмежених умовах у специфікацію нормалізованих розмірів заготовок, призначених для моделювання допустимих карт розкрою. Комбіновані заготовки можуть знаходитися в будь-якому місці довільної карти розкрою.

Проведений аналіз стану проблеми виготовлення розкрійного обладнання свідчить про те, що за останні десятиліття спостерігається перехід від створення та реалізації окремих видів верстатів і потокових ліній до розроблення і широкого впровадження у виробництво автономних розкрійних систем і спеціальних комплексів.

У спрощеному вигляді представлено компонувальні схеми пилкових установок сучасного автоматизованого обладнання. Їх узагальнений характер є основою як для звичайних ліній розкрою, так і для спеціальних систем розкрою з різними їх модифікаціями та конструктивними уточненнями.

Внаслідок системного аналізу особливостей функціонування наявних технологічних процесів виготовлення заготовок, а також технологічних можливостей сучасного розкрійного обладнання розроблено заходи щодо підвищення ефективності ТП розкрою, основними з яких є: ускладнення конфігурацій карт розкрою; додатковий розкрій залишків смуг; введення у карти розкрою комбінованих заготовок; застосування вкладених карт розкрою; удосконалення конструкцій ліній розкрою.

З огляду на структуру заходів виникає проблема вибору такого ТП розкрою, який характеризуватиметься найменшими загальними витратами на виготовлення заготовок.

За критерій його оптимізації доцільно прийняти мінімальну суму виробничих витрат (), яка складається з загальної вартості використаних плит (), з собівартості процесу розкрою плит на основному () та їх залишків на допоміжному () обладнанні, а також собівартості процесу виготовлення заготовок з кускових відходів (), тобто

.

З'ясовано, що збільшення виходу заготовок на 1 % з одиниці площі розкроюваного матеріалу (наприклад, з 92 до 93 %) при постійних обсягах їх виготовлення призводить до зменшення вартості використаного матеріалу на 1.17 %, а значить і до зменшення суми виробничих витрат та збільшення прибутків підприємства на 1.09 %. Тому матеріалозбереження, яке характеризується підвищенням ефективності використання плит як сировини, можна вважати показником відносної переваги одного ТП розкрою над іншим.

Однак проведені практичні дослідження ТП розкрою свідчать про те, що навіть незначне підвищення ефективності використання плит вимагає залучення додаткових виробничих ресурсів, внаслідок чого наступає такий момент, коли виробничі видатки можуть значно перевищувати отриманий виграш від заощадженої сировини. У роботі на підставі економіко-математичного аналізу теоретично обґрунтовано і практично доведено, що оптимальний рівень використання плит з огляду на ефективність роботи підприємства знаходиться у межах максимальної рентабельності процесу виготовлення заготовок, а з огляду на зацікавленість споживачів, які погоджуються покрити різницю між вартістю реалізації заготовок та собівартістю процесу їх виготовлення, - у межах максимального прибутку підприємства. Тому ресурсозбереження, яке характеризується оптимальною ефективністю використання плит як сировини, можна вважати показником відносної переваги одного ТП розкрою над іншим.

У третьому розділі розглядається структурно-функціональний аналіз (СФА) ТП розкрою, а саме: наведено постановку загальної задачі системного аналізу ТП розкрою; подано формалізований опис задачі СФА ТП розкрою та наведена загальна стратегія її розв'язання; розроблено формалізований опис задачі системної оптимізації структури та параметрів проектованої лінії розкрою.

Наведено постановку загальної задачі системного аналізу ТП розкрою, яка складається з послідовної реалізації задачі СФА ТП розкрою, задачі аналізу управління процесом його функціонування та задачі техніко-економічного аналізу. Методологічні підходи до їх розв'язання розвиваються завдяки широкому застосуванню евристичних прийомів і методів створення інтелектуальних засобів підтримки рішень на основі систематизації, узагальнення та нагромадження знань і досвіду дослідників з різних галузей науки і техніки.

Розроблено формалізований опис задачі СФА ТП розкрою, основне завдання якої полягає у його зведенні до певної ієрархічної структури та визначенні функціональних елементів, що дає змогу істотно спростити процес її розв'язання як на етапі проектування, так і на етапі експериментального випробування. Позаяк реалізація ТП розкрою здійснюється за допомогою лінії розкрою, то вона може складатися з різного устаткування - завантажувального, передавального, розкрійного, розвантажувального тощо. Кожне устаткування виконує певні функції, має свої індивідуальні властивості, які у сукупності реалізують властивості лінії розкрою.

Формалізований опис задачі СФА ТП розкрою складається з послідовної реалізації таких часткових задач:

задачі декомпозиції вимог до проектованої лінії розкрою:

; ; ;(10)



задачі формування багаторівневої структури лінії розкрою:

; ; ;(11)

задачі раціонального вибору параметрів функціональних елементів проектованої лінії розкрою:

(12)

задачі багатокритеріальної оцінки якості отриманих показників лінії розкрою:

, (13)

де: - функціонал, який здійснює перетворення множини вимог до властивостей q-го ієрархічного рівня на вимоги до властивостей j-го функціонального елемента; - функціонал, який здійснює перетворення конструкції лінії розкрою на конструкцію q-го ієрархічного рівня; - функціонал, який здійснює зворотне перетворення конструкції q-го ієрархічного рівня на конструкцію лінії розкрою; , - нечіткі відношення, які визначають взаємозв'язок загальних вимог до властивостей лінії розкрою і загальних параметрів її конструкції.

Задача вибору раціональної кількості ієрархічних рівнів лінії розкрою має такий формалізований опис.

Визначено: узагальнену цільову функцію проектованої лінії розкрою



(14)

на основі функції перетворення загальних показників якості до функціональних елементів у раціональну її ієрархічну структуру

, (15)

а також функції оцінки якості отриманого варіанту її раціональної структури під час v-ої спроби відбору

(16)

і з врахуванням функції обмеження загальних витрат на її створення

. (17)

Потрібно: знайти таку раціональну кількість ієрархічних рівнів лінії розкрою, щоб для всіх ризиків у разі реалізації заданих вимог витрати не перевищували допустимих значень .

Адаптовано узагальнений алгоритм розв'язання задачі СФА складних ієрархічних систем до задачі СФА ТП розкрою, основна мета якого - показати, що за заданими вимогами принципово можливо або неможливо реалізувати лінію розкрою з певними її властивостями за наявних технологій промислового виробництва або у разі впровадження апробованих нових технологій. Розроблено формалізований опис задачі параметричної оптимізації технічних характеристик функціональних елементів лінії розкрою, реалізація якої дає змогу знайти раціональний компроміс між суперечливими вимогами до їх технічних параметрів та техніко-економічних показників ефективності її роботи.

У четвертому розділі розроблено комбінаторні методи моделювання допустимих карт розкрою, зокрема: наведено формалізований опис процесу моделювання карт розкрою у вигляді послідовної реалізації таких часткових задач: підготовки розмірів заготовок; декомпозиції складних карт розкрою; безпосереднього процесу моделювання допустимих карт розкрою. Розроблено математичні моделі та методи моделювання допустимих карт розкрою, яким належать: задачі одновимірного розміщення прямокутних об'єктів (ПО) вздовж смуги скінченої довжини; задачі двовимірного та багаторівневого розміщення ПО у межах прямокутної площини (ПП).

Системний аналіз способів розкрою плит на заготовки, а також детальний аналіз технологічних можливості сучасного розкрійного обладнання вказують на потребу декомпозиції складних карт розкрою, тобто поділу їх на ієрархічні рівні та відповідні їм функціональні елементи. Запропоновано під ієрархічним рівнем використовувати таке поняття як абстрактна частина плити (АЧП), а під поняттям функціональний елементи - відповідну базову конфігурацію карти розкрою. Для АЧП розроблено основні принципи моделювання базових конфігурацій карт розкрою. Зокрема, для всієї плити чи її ділянок, а також для торцевої та основної частин плити пропонується у основу базової конфігурації карти розкрою закласти: схему "сітка" комбінацію багатьох "сіток" гільйотинне відрізання смуг. Для моделювання базових конфігурацій карт розкрою розроблено метод регулярного послідовно-одиночного одно- та двовимірного і багаторівневого розміщування ПО у межах АЧП з врахуванням різних обмежень та вимог.

У роботі детально розглядаються три групи комбінаторних задач розміщування ПО. До першої групи належать задачі, які стосуються розкрою погонного матеріалу на заготовки (1D пакування ПО). Для таких задач допустимі карти розкрою моделюються з використанням методу РП-ООР ПО вздовж смуги скінченої довжини. До другої групи належать задачі, які стосуються розкрою плит на заготовки (2D пакування ПО), тобто від плити спочатку поздовжніми пропилами відрізаються смуги, а потім ці смуги разом розрізаються на заготовки. У цій групі задач карти розкрою моделюються з використанням методу РП-ОДР ПО у межах АЧП за схемою "сітка". До третьої групи належать задачі, які стосуються розкрою плит на заготовки (2D пакування ПО), але у картах спочатку відбувається розміщування смуг по ширині плити, після чого здійснюється їх розкладання одна під одною, а потім - розміщуються заготовки вздовж кожної розкладеної смуги. Тут карти розкрою моделюються з використанням методу РП-ОБрР ПО у межах АЧП з комбінацією багатьох "сіток". До цієї групи задач також належать карти, які реалізуються за схемою гільйотинного розкрою.

У наростаючому порядку складності вирішуваних задач розроблено процедури моделювання усіх допустимих карт розкрою, математичні моделі яких враховують відомі на сьогодні як різні за складністю концептуальні схеми розкрою, так і для кожної з них відповідні базові конфігурації карт розкрою. Наведено особливості моделювання комбінованих карт розкрою для всієї плити, її торцевої та основної частин і вкладених карт розкрою, а також проаналізовано допустимі варіанти додаткового розкрою залишків смуг і залишків ширини плити.

У роботі для реалізації методу двовимірного та багаторівневого розміщування ПО у межах АЧП введено такі позначення для вхідних даних:

Д^п, Ш^п - довжина і ширина АЧП, m^с - кількість смуг;

- впорядковані за спаданням ширини смуг;

- кількість ПО у смугах;

- впорядковані за спаданням довжини ПО у кожній смузі.

Процедура моделювання всіх допустимих карт розкрою за схемою "сітка" без врахування обмежень на процес їх генерування полягає у послідовному розв'язанні таких задач: задачі 1D пакування ПО у межах основної смуги; задачі підбору допоміжних смуг, до яких входили б усі ПО з довжинами, як і у основній смузі; задачі 1D пакування підібраних ширин смуг у межах ширини АЧП. Їх послідовна реалізація дає змогу отримати такі результату розрахунку:

допустимі карти розміщення ПО у межах АЧП за схемою "сітка"

; (18)

інтенсивність заповнення ПО усієї АЧП

; (19)

повторюваності ПО у основній та допоміжних смугах

...