Гуляницький, Леонід ФедоровичДубіна, Анастасія Володимирівна2022-04-142022-04-142021-05Дубіна, А. В. Оптимізація розміщення прямокутників на напівнескінченній стрічці : магістерська дис. : 126 Інформаційні системи та технології / Дубіна Анастасія Володимирівна. – Київ, 2021. – 134 с.https://ela.kpi.ua/handle/123456789/46881Магістерська дисертація: 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перестановкирозміщення прямокутниківтеорія розкладівкомбінаторна оптимізаціяжадібний алгоритмлокальний пошуктабуйований пошукpermutationplacement of rectanglesschedule theorycombinatory optimizationgreedy algorithmlocal searchtabu searchMaster Thesis134 с.519.854.2