АЛГОРИТМ ПЕРЕМІШАНИХ СТРИБАЮЧИХ ЖАБ У ЗАДАЧІ РОЗМІЩЕННЯ ВИРОБНИЦТВА

Анотація

Задача розміщення виробництва – одна з найвідоміших масових задач дискретної оптимізації. Є безліч варіантів постановки цієї задачі. Як правило, всі ці варіанти задачі розміщення виробництва належать до класу NP-важких задач, тобто для пошуку точного розв’язку такої задачі на сьогодні невідомі алгоритми поліноміальної трудомісткості. Досі не розроблено ефективних способів розрахунку нижніх границь оцінки цільової функції для такої задачі. Точні алгоритми для цієї задачі зводяться до перебору варіантів. У зв’язку з цим використання точних алгоритмів для вирішення задачі розміщення виробництва часто виявляється недоцільним і неможливим через великі витрати часу. Тому значний інтерес становить розробка та дослідження евристичних методів оптимізації. Одним із перспективних напрямів є розробка алгоритмів, заснованих на відомих метаевристичних підходах, які з успіхом використовуються для вирішення багатьох задач дискретної оптимізації. У цій роботі показано, що один з класів задач розміщення виробництва зводиться до задачі покриття повного графа зірками, що не перетинаються у вершинах. Доведено, що в такій постановці задачу можна розглядати як задачу оптимізації на орієнтованій фрагментарній структурі. Це дозволяє створювати гібридні алгоритми відшукання субоптимальних розв’язків задач такого класу на основі комбінації відомої метаевристики та фрагментарного алгоритму. В роботі розглянута одна з таких метаевристик, а саме алгоритм перемішаних стрибаючих жаб. Показано, що цей алгоритм може бути використаний для пошуку субоптимальних рішень задачі оптимізації на множині перестановок. З іншого боку, за наявності орієнтованої фрагментарної структури задача дискретної оптимізації може бути зведена до задачі оптимізації на множині перестановок. Таким чином, отримано простий та досить ефективний метод відшукання субоптимальних розв’язків задачі розміщення виробництва. Метод може бути легко перенесений і на інші класи задач дискретної оптимізації, які можуть розглядатися як задачі оптимізації на орієнтованій фрагментарній структурі.