Оптимізація розміщення прямокутників на напівнескінченній стрічці

Скорочена інформація про документ
dc.contributor.advisorГуляницький, Леонід Федорович
dc.contributor.authorДубіна, Анастасія Володимирівна
dc.date.accessioned2022-04-14T10:38:57Z
dc.date.available2022-04-14T10:38:57Z
dc.date.issued2021-05
dc.description.abstractenMaster's dissertation: 134 pp., 35 figs., 44 tables, 65 sources, 1 appendix. Topicality. The problem of placing rectangles on a semi-infinite tape in the modern world has a practical application and various variations: the problem of packing rectangles, the problem of scheduling and others. Within the framework of calendar planning it is expedient to consider methods and models of the theory of schedules. Since most problems of schedule theory are classified as problems of NP complexity, it is impossible to find exact solutions in a reasonable time. In this case, only the search for local optimums is possible, using approximate algorithms. Geometric placement problems are widely used in various fields. The task of placement is to determine the optimal position of a finite number of geometric objects in a given area, taking into account various constraints. Technological processes usually use the stage of cutting or placement of parts. This step is important because it can save resources, but it is time consuming due to the need to find the optimal solution. This stage can be described by optimization problems of geometric placement. The classical problems of the studied type include the problems of cutting and packaging, geometric placement. Connection of work with scientific programs, plans, themes. The work was performed at the Department of Automated Information Processing and Control Systems of the National Technical University of Ukraine "Kyiv Polytechnic Institute. Igor Sikorsky »» within the theme "Effective methods for solving problems of schedule theory" (№ DR 0117U000919). The purpose of the study is to modify and improve the algorithms for placing rectangles on a semi-infinite tape to reduce its length. To achieve this goal must perform the following tasks: determine the class of tasks to which this task belongs; review existing methods for solving rectangle placement problems; develop an algorithm for solving the placement problem (greedy, local algorithms and search taboos); develop a software implementation of the above algorithms; perform an analysis of the results of the study. The object of study is the process of placing rectangles on a semi-infinite tape. The subject of research - models and methods of optimizing the placement of rectangles. The scientific novelty of the obtained results will be improve existing algorithms for placing rectangles on a semi-infinite tape. Publications. Materials of the work are published in the collections: Scientific support of technological progress of the XXI century: materials of the international scientific conference (Vol. 2) (2020, Chernivtsi), Proceedings of the International Scientific and Practical Conference (2019, Valletta), Science and Technology of the XXI Century: Proceedings of the XXI International Students R&D Online Conference (2020, Kyiv), VI All-Ukrainian scientific-practical conference of young scientists and students "Information systems and management technologies" (ISTU-2021, Kyiv); and in the professional edition - Scientific Bulletin of Uzhhorod University, series "Mathematics and Informatics".uk
dc.description.abstractukМагістерська дисертація: 134 с., 35 рис., 44 табл., 65 джерел,1 додаток. Актуальність. Задача розміщення прямокутників на напівнескінченній стрічці в сучасному світі має практичне застосування та різні варіації: задача упаковки прямокутників, задача календарного планування та інші. В рамках календарного планування доцільно розглядати методи та моделі теорії розкладів. Оскільки більша частина задач теорії розкладів класифікується як задачі, що мають NP складність тому знаходження точних розв’язків за прийнятний час є неможливим. В такому випадку, можливий лише пошук локальних оптимумів, за допомогою наближених алгоритмів. Задачі геометричного розміщення широко використовуються в різних сферах. Задача розміщення полягає у визначенні оптимального положення скінченної кількості геометричних об’єктів в заданих областях з урахуванням різноманітних обмежень. Технологічні процеси зазвичай використовують етап розкрою чи розміщення деталей. Цей етап важливий, оскільки можна досягти економії ресурсів, але він є трудомістким за рахунок необхідності пошуку оптимального розв’язку. Цей етап можна описати оптимізаційними задачами геометричного розміщення. До класичних задач досліджуваного типу відносяться задачі розкрою та упаковки, геометричного розміщення. Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках теми «Ефективні методи розв'язання задач теорії розкладів» (Державний реєстраційний номер 0117U000919). Мета дослідження – розробка та модифікація алгоритмів розміщення прямокутників на напівнескінченній стрічці для зменшення її довжини. Для досягнення мети необхідно виконати наступні завдання: визначити клас задач, до якого відноситься дана задача; виконати огляд існуючих методів розв’язування задач розміщення прямокутників; розробити алгоритм розв’язування задачі розміщення (жадібний, алгоритми локального та табу пошуку); розробити програмну реалізацію вищезгаданих алгоритмів; виконати аналіз отриманих результатів дослідження. Об’єкт дослідження – процес розміщення прямокутників на напівнескінченній стрічці. Предмет дослідження – моделі та методи оптимізації розміщення прямокутників. Наукова новизна одержаних результатів полягатиме удосконаленні існуючих алгоритмів розміщення прямокутників на напівнескінченній стрічці. Публікації. Матеріали роботи опубліковані у збірниках: Наукового забезпечення технологічного прогресу XXI сторіччя: матеріали міжнародної наукової конференції (Т.2) (2020р, м. Чернівці), Proceedings of the International Scientific and Practical Conference (2019 р. м. Валета), Science and Technology of the XXI Century: Proceedings of the XXІ International Students R&D Online Conference (2020 р, м.Київ), VІ Всеукраїнська науково-практична конференція молодих вчених та студентів «Інформаційні системи та технології управління» (ІСТУ-2021, м. Київ); та у фаховому виданні – Науковий вісник Ужгородського університету, cерія «Математика і інформатика».uk
dc.format.page134 с.uk
dc.identifier.citationДубіна, А. В. Оптимізація розміщення прямокутників на напівнескінченній стрічці : магістерська дис. : 126 Інформаційні системи та технології / Дубіна Анастасія Володимирівна. – Київ, 2021. – 134 с.uk
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/46881
dc.language.isoukuk
dc.publisherКПІ ім. Ігоря Сікорськогоuk
dc.publisher.placeКиївuk
dc.subjectперестановкиuk
dc.subjectрозміщення прямокутниківuk
dc.subjectтеорія розкладівuk
dc.subjectкомбінаторна оптимізаціяuk
dc.subjectжадібний алгоритмuk
dc.subjectлокальний пошукuk
dc.subjectтабуйований пошукuk
dc.subjectpermutationuk
dc.subjectplacement of rectanglesuk
dc.subjectschedule theoryuk
dc.subjectcombinatory optimizationuk
dc.subjectgreedy algorithmuk
dc.subjectlocal searchuk
dc.subjecttabu searchuk
dc.subject.udc519.854.2uk
dc.titleОптимізація розміщення прямокутників на напівнескінченній стрічціuk
dc.typeMaster Thesisuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
Dubina_magistr.pdf
Розмір:
3.4 MB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
9.1 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Магістерські роботи (АСОІУ)
Магістерські роботи