Оптимізація розміщення прямокутників на напівнескінченній стрічці
Вантажиться...
Дата
2021-05
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Магістерська дисертація: 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ерія «Математика і інформатика».
Опис
Ключові слова
перестановки, розміщення прямокутників, теорія розкладів, комбінаторна оптимізація, жадібний алгоритм, локальний пошук, табуйований пошук, permutation, placement of rectangles, schedule theory, combinatory optimization, greedy algorithm, local search, tabu search
Бібліографічний опис
Дубіна, А. В. Оптимізація розміщення прямокутників на напівнескінченній стрічці : магістерська дис. : 126 Інформаційні системи та технології / Дубіна Анастасія Володимирівна. – Київ, 2021. – 134 с.