Методи планування розподілу задач в багатопроцесорних системах

Abstract

Метою даної кваліфікаційної роботи є розроблення та порівняльний аналіз ефективності наближених алгоритмів, що базуються на ранговому методі, для вирішення задачі балансування навантаження. Ця задача може бути формалізована у вигляді задачі цілочисельного лінійного програмування з булевими змінними (ЦЛП з БЗ). Об'єктом дослідження є алгоритми пошуку рішень, що використовують різні підходи до реалізації стратегій відсікання, а також аналіз їх впливу на загальну продуктивність програмної реалізації. Предметом дослідження виступає ранговий метод та його застосування у процесі оптимального розподілу навантаження в багатопроцесорних обчислювальних системах. У ході виконання кваліфікаційної роботи було оглянуто сучасні рішення в сфері балансування навантаження в мережі, наведено доказ зводимості даного завдання до вирішення класичної задачі "Про ранець 0-1" і, відповідно, приведено огляд деяких відносно нових рішень даної задачі. Запропонована програмна реалізація деяких наближених алгоритмів пошуку рішення задачі "Про ранець 0-1", заснованих на моделі рангового підходу зі скороченням кількості аналізованих векторів рішення за методом відсівання безперспективних варіантів. Виявлено потенційні вузькі місця вже відомих стратегій відсікання, та запропоновано модифіковану версію однієї з них.