Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Կամայական ուրվագծով երկչափ մարմինների ձևման խնդրի հետազոտություն և ծրագրային համակարգի մշակում

Քեյան, Արթուր Ժորայի (2016) Կամայական ուրվագծով երկչափ մարմինների ձևման խնդրի հետազոտություն և ծրագրային համակարգի մշակում. PhD thesis, ՀՀ ԳԱԱ Ինֆորմատիկայի և ավտոմատացման պրոբլեմների ինստիտուտ.

[img] PDF (Thesis)
Available under License Creative Commons Attribution.

Download (13Mb)
    [img] PDF (Abstract)
    Available under License Creative Commons Attribution.

    Download (3977Kb)

      Abstract

      Այսօր արտադրության ոլորտում բնորոշ է ինֆորմացիոն տեխնոլոգիաների կիրառությունը՝ հումքի կորուստները առավելագույնս նվազեցնելու նպատակով, ինչը բավական կարևոր է շուկայական հարաբերություններում: Արտադրող տարբեր սուբյեկների առաջ խնդիր է դրված առավելություն ձեռք բերել մրցակցային պայքարում նոր տեխնոլոգիաների կիրառության շնորհիվ նյութական ծախսերի մակարդակը նվազեցնելու միջոցով: Դրան կարելի է հասնել ներդնելով արդյունավետ մաթեմատիկական մեթոդներ և ծրագրային միջոցներ: Իրական կյանքի արտադրության պայմաններում կոմբինատոր օպտիմիզացիայի խնդիրների մի դաս են կազմում ձևման և փաթեթավորման խնդիրները, որոնք համակարգչային գիտության ոլորտում դասական և դժվարին խնդիրների ցանկում են : Այս խնդիրները ուսումնասիրվել են տասնյակ տարիներ, և այսօր աշխատանքները շարունակվում են գտնելու նոր մոտեցումներ և ավելի լավ արդյունքներ: Վերջին տարիներին այս խնդիրների նկատմամբ աճող հետաքրքրությունը պայմանավորված է դրանց տեսական բարդությամբ և կիրառությունների բազմազանությամբ: Այս տիպի խնդիրները պատկանում են NP լրիվ դասին, այսինքն հնարավոր չէ գտնել ալգորիթմ, որը որոշի օպտիմալ լուծումը բազմանդամային ժամանակում: Հաջողվում է միայն գտնել մոտարկող ալգորիթմներ, որոնք օպտիմալին ամենամոտ հնարավոր լուծումն են առաջարկում: Կան խնդրի բազմապիսի տարբերակներ կախված կիրառություններից, ինչպես նաև բազմապիսի մոտեցումներ դրանց լուծման համար: Այդ խնդիրները բաժանվում են ենթադասերի ըստ չափողականության (միաչափ, երկչափ և եռաչափ) կախված կիրառական մեկնաբանությունից: Ալգորիթմները դասակարգվում են նաև որպես առցանց (online) և արտացանց (offline) խմբերի: Առցանց տարբերակում դետալները հարկավոր է փաթեթավորել կամ ձևել ըստ դրանց հայտվելու հերթականության, չունենալով ինֆորմացիա հաջորդների մասին, ի տարբերություն արտացանց դեպքին, երբ դետալների ամբողջ բազմությունը նախորոք հայտնի է, և կարելի է դրանց հերթականությունը փոխել: Այս աշխատանքը նվիրված է արտացանց երկչափ ձևման խնդիրների ուսումնասիրությանը, երբ հարկավոր է սահմանափակ հումքից, օրինակ, փայտից, կաշվից, մետաղից կամ թղթից, ձևել տարբեր ավելի փոքր չափի դետալներ, որոնց ցուցակը հայտնի է: Խնդրի նպատակն է հումքի մաքսիմալ օգտագործումը կամ կորուստների նվազեցումը: Հումքի օպտիմալ օգտագործման խնդրի լուծմանը վերաբերվող բազմաթիվ հոդվածներ են հրապարակվել : Գծային ծրագրավորման դասական մեթոդները, որոնք հաջողությամբ կիրառվում են մասսայական արտադրության դեպքում, դժվար կիրառելի են անհատական արտադրության պայմաններում, երբ լինում են անհատական պատվերներ, և որպես կանոն օգտագործվում է թանկարժեք հումք: Ճշգրիտ օպտիմալ լուծումը հնարավոր է միայն հատարկման եղանակով, ինչը պրակտիկայում հնարավոր չէ կիրառել ժամանակի մեծ կորուստների պատճառով: Այդ իրավիճակում մեծ ուշադրություն է հատկացվում էվրիստիկ ալգորիթմների մշակմանը և հետազոտմանը: Դրանց արդյունավետությունը ստուգվում է փորձարկումների միջոցով: Հաշվողական ժամանակի էական ծախսի և տեխնոլոգիական սահմանափակումների պայմաններում սովորաբար կիրառվում են ծրագրային համակարգեր: Սակայն երկչափ ձևում իրականացնող գոյություն ունեցող հասանելի համակարգերը աշխատում են միայն ուղղանկյունների հետ, մինչդեռ շատ կիրառություններում, օրինակ, կաշվի իրերի արտադրությունում, առկա են կամայական ուրվագծով երկչափ մարմիններ: Այս իրավիճակում արդիական էր մշակել նոր էվրիստիկ ալգորիթմ և ծրագրային համակարգ, որը կիրականացներ կամայական ուրվագծով երկչափ մարմինների արդյունավետ ձևումը: Проблема упаковки и раскроя является одним из классических и сложных проблем в области информационных технологий. Эта проблема была изучена много лет, и сегодня исследования продолжаются, чтобы найти новые подходы и лучшие результаты. Существуют различные варианты задачи и подходы к их решению, много работ опубликовано относительно этой проблемы. Поскольку задачи упаковки и раскроя относятся к классу NP-полных задач, то возможно только нахождение приближенных алгоритмов, наиболее близких к оптимальному. Задачи раскроя и упаковки можно разелить на подклассы по размерности (1D,2D, 3D) в зависимости от прикладной интерпретации. Алгоритмы классифицируются также как online и offline, когда список деталей, подлежащих раскрою, заранее не известен или известен. Данная работа посвящена исследованию задачи двумерного offline раскроя, когда имеется ограниченное сырье, например дерево, кожа, метал или бумага, и более мелкие детали произвольной формы. Цель задачи максимальное использование сырья или уменьшение отходов. В условиях технологических ограничений и существенной траты вычислительного времени обычно применяют программные средства. Однако существующие доступные системы двумерного раскроя работают только с прямоугольниками, в то время, как во многих приложениях, имеются детали произвольной формы. Целью научной работы является разработка программной системы, осуществляющей раскрой двумерных деталей произвольного контура. Для достижения данной цели разработаны математические модели, новый эвристический алгоритм и комплекс программ для решения задачи раскроя деталей произвольного контура. Алгоритма решения задачи раскроя двумерных деталей произвольного контура в литературе найдено не было, подобное решение предлагается впервые. В работе предложены новые подходы, а также модификации известных методов для моделирования и дискретизации деталей. Предложен новый эвристический алгоритм раскроя двумерных деталей произвольного контура. Разработана библиотека matrix.dll функций работы с матрицами. Разработа программа раскроя двумерных деталей произволного контура, в отличии от других программ двумерного раскроя, которые работают только с прямоуголниками. Разработанная с простым и доступным интерфейсом система MIC Host позволяет моделировать реальные детали, а также сырье с дефектами. Она осуществляет раскрой с учетом дефектов сырья. Система внедрена на двух частных деревообрабатывающих производственных участках. В результате применения системы увеличилась эффективность производства, сократились расходы более чем на 20 %. Рассмотренные в диссертации модели и предложенные решения универсальны и могут быть использованы в различных областях производста. В работе получены следующие основные результаты: Разработаны метод и програмная среда моделирования двумерных деталей произвольного контура. Включены инструменты для создания простых геометрических объектов, для их изменения, а также для создания сложных контуров. [1] Предложен метод для дискретизации геометрических моделей. [2] Предложен эвристический offline алгоритм для эффективного решения задачи раскроя двумерных деталей произвольного контура.[3] Разработана библиотека функций matrix.dll для работы с матрицами.[3] Разработана система раскроя двумерных деталей произвольного контура с учетом свойств данного сырья.[3] Диссертация состоит из введения, четырех глав, заключения, списка литературы с 106 ссылками. Общий объем диссертации составляет 100 компьютерных страниц. The cutting and bin packing problem is one of the classic and challenging problems in the field of computer science. This problem has been studied many years and to this date work is going on to find new improvised approaches and better results. There are different variants of the problem and similarly several approaches for tackling them, a lot of papers have been published relating to this problem. Since bin packing belongs to the class of NP hard problems, it is really difficult to come up with a polynomial time algorithm which solves the problem to give an optimal solution. So as a result, approximation algorithms are presented to find the possible solution closest to the optimal. The cutting and packing ploblems can be classified into subclasses by dimension (1D, 2D, 3D) depending on the application interpretation. Algorithms are also classified as online and offline, when the list of items for cutting are previously unknown or known. This work is devoted to the investigation of the problem of two-dimensional offline cutting when there is a limited raw materials, such as wood, leather, metal or paper, and a list of arbitrary shaped details. The purpose of the task is to maximize the use of raw materials or the reducing of waste. In the conditions of technological constraints and significant waste of computing time ussually software systems are used. Actually there are some existing softs that can solve this issue, but they do not work with irregular shapes, only with rectangles. The aim of this research is to develop a software system implementing the cutting of two-dimensional irregularly shaped objects. To achieve this goal, mathematical models, a new heuristic algorithm and a software package are developed for solving the problem of cutting two-dimensional irregularly shaped objects. Algorithms for solving the problem of cutting of two-dimensional irregularly shaped objects were not found in the literature, such a solution is offered for the first time. In this work we propose new approaches, as well as modifications of known techniques for modeling and discretization of details. A new heuristic algorithm for cutting two-dimensional irregularly shaped objects is proposed. A library matrix.dll of functions for matrices is developed. A software tool of cutting two-dimensional irregularly shaped objects is created, unlike the other two-dimensional cutting programs that work only with rectangles. Designed with a simple and accessible interface MIC Host system allows to model the real details, as well as raw materials with defects. It performs cutting taking into account the raw material defects. The system was applied on two private wood production areas. As a result of the application of the system the efficiency was increased, the costs were reduced by more than 20%. The considered in the dissertation models and the proposed solutions are universal and can be used in various production fields. Thus, the main results of the work are the following: A method and a software environment is implemented for modeling of two - dimensional irregularly shaped objects. It includes tools for creating simple geometrical objects, for manipulating with them and for creating complex shapes from real life objects. [1] A method of discretization of geometric models is proposed. [2] A heuristic offline algorithm for the effective solution of the two - dimensional irregularly shaped objects cutting problem is suggested. [3] A library matrix.dll of functions for matrices is developed. [3] A software system for cutting two-dimensional irregularly shaped objects is created, taking into account the properties of the raw material. [3] The dissertation includes the introduction, four chapters, the conclusion, bibliography with 106 sources. The work consists of 100 printed pages.

      Item Type: Thesis (PhD)
      Additional Information: Исследование задачи раскроя двумерных деталей произвольной формы и разработка программной системы. Investigation of the cutting problem of irregularly shaped two-dimensional objects and development of software system.
      Uncontrolled Keywords: Кеян Артур Жораевич, Keyan A.
      Subjects: Informatics and Computer Systems
      Divisions: UNSPECIFIED
      Depositing User: NLA Circ. Dpt.
      Date Deposited: 14 Nov 2016 15:20
      Last Modified: 14 Nov 2016 15:20
      URI: http://etd.asj-oa.am/id/eprint/3769

      Actions (login required)

      View Item