Остання редакція: 2024-12-15
Анотація
В комбінаторній оптимізації можна навести багато прикладів, коли задачі різних класів розв’язуються за однією і тією ж обчислювальною схемою. Така ситуація пов’язана із властивістю подібності різних задач цього класу. Щоб розробляти універсальні методи та алгоритми для їхнього розв’язання необхідно виявити характерні ознаки цієї подібності. Ця властивість розглянута на прикладі задачі планування з теорії розкладів та проблеми розподілу задач в рої безпілотних літальних апаратів (БПЛА).
Одна із задач планування з теорії розкладів формулюється так. Задано деяку кількість деталей. Кожна з них повинна пройти послідовну обробку на певній машині. Необхідно скласти такий розклад обробки деталей, щоб використаний на ці операції час був би мінімальний за умови, що він не перевищує заданої величини. В цій задачі кожна деталь потребує для свого обробітку одну операцію. Кожна машина також виконує одну операцію.
Одна з проблем розподілу задач в рої БПЛА ґрунтується на механізмі послідовності виконання завдань. Рій складається з великої кількості невеликих безпілотників, які мають обмежені ресурси для виконання завдань і працюють здебільшого автономно у режимі реального часу. Встановлюючи послідовність завдань, кожен БПЛА чітко розділяє необхідний час виконання завдання та час очікування синхронізації. Для знайдених нових цілей кожен БПЛА швидко визначає свій доступний період часу.
В обох задачах задано певну кількість машин (або безпілотників), які виконують задану операцію (обробку деталей або завдання, яке передається з попереднього БПЛА ). Ці операції виконуються послідовно. Час, затрачений на виконання певного завдання в обох задачах, постійний. Змінюється лише час простою. Проблема оптимізації в обох наведених задачах зводиться до мінімізації часу простою (або синхронізації). Обидві задачі відносяться до теорії розкладів. Оскільки в них має місце перебір варіантів їх змодельовано в рамках теорії комбінаторної оптимізації. Аргументом цільової функції в них є така комбінаторна конфігурація, як розміщення без повторень. Тобто, вони подібні також і за аргументом цільової функції. За цією ознакою описані задачі розв’язують одними і тими ж підходами: алгоритмом з використанням структурно-алфавітного пошуку та динамічним програмуванням.
Ключові слова
Посилання
[1] Н. К. Тимофієва, В.І. Гриценко. Розв’язання задачі планування з теорії розкладу методом структурно-алфавітного пошуку та гібридним алгоритмом. УСиМ. 2011. № 3. С.21 – 36.
[2] Xiaowei fu, Peng feng, Xiaoguang Gao. Swarm. “UAVs Task and Resource Dynamic Assignment Algorithm Based on Task Sequence Mechanism”, in Digital Object Identifier 10.1109.ACCESS.2019. p. 41090–41100.
[3 Н.К. Тимофієва Теоретико-числові методи розв'язання задач комбінаторної оптимізації. – Дисертація на здобуття наукового ступеня доктора технічних наук за спеціальністю 01.05.02 – математичне моделювання та обчислювальні методи. Рукопис. – ІК ім. В.М. Глушкова НАН України, К. 2007. 374 с.