АЛГОРИТМИ ЛОКАЛЬНОГО ПОШУКУ ДЛЯ ОДНІЄЇ ЗАДАЧІ ПЛАНУВАННЯ ВИКОНАННЯ РОБІТ

Анотація

Розглядається задача планування виконання робіт декількома пристроями. Характеристиками розглянутої задачі є наявність загального директивного строку для всіх пристроїв, різна непропорційна продуктивність пристроїв, наявність відношення часткового строгого впорядкування між роботами та визначена для кожної з робіт важливість. Наведено змістовну та математичну постановки задачі, що розглядається. Запропоновано два алгоритми локального пошуку для розв’язування цієї задачі: алгоритм детермінованого локального пошуку та алгоритм імітаційного відпалу. Наведено ключові аспекти реалізації для запропонованих алгоритмів, схеми алгоритмів та порівняння результатів їх роботи на 16 наборах тестових даних.

Ключові слова: оптимальне планування, розклад, різна продуктивність, директивний термін, паралельні пристрої, алгоритм детермінованого локального пошуку, алгоритм імітаційного відпалу.

Галкина Г. А. Алгоритмы локального поиска для одной задачи планирования выполнения работ / Национальный технический университет Украины «Киевский политехнический институт имени Игоря Сикорского», Украина, Киев

Рассматривается задача планирования выполнения работ несколькими устройствами. Характеристиками рассмотренной задачи являются наличие общего директивного срока для всех устройств, разная непропорциональная продуктивность устройств, наличие отношения частичной строгой упорядоченности между работами и определённая для каждой из работ важность. Приведены смысловая и математическая постановки рассматриваемой задачи. Предложены два алгоритма локального поиска для решения этой задачи, алгоритм детерминированного локального поиска и алгоритм имитации отжига. Приведены ключевые аспекты реализации предложенных алгоритмов, схемы алгоритмов и сравнение результатов их работы на 16 различных наборах входных данных.

Ключевые слова: оптимальное планирование, расписание, разная продуктивность, директивный срок, параллельные устройства, алгоритм детерминированного локального поиска, алгоритм имитации отжига.

H. Halkina Local search algorithms for one optimal scheduling problem / National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, Ukraine, Kyiv

The problem of scheduling work for a set of machines is considered. The main characteristics of the problem include the existence of a common due date for all the machines, different unrelated productivity of the machines, the partial strict ordering set for the tasks and the value set for each of the tasks to be scheduled. The semantic and formal models of the problem are specified. Two local search algorithms are suggested: a deterministic local search algorithm and a simulated annealing algorithm. Key implementation points for each of the algorithms are covered; the algorithms’ as sequences of steps are described and a comparison of the suggested algorithms’ results when used on 16 input data sets is performed.

Keywords: optimal scheduling, schedule, different productivity, due date, parallel machines, deterministic local search, simulated annealing.