Результаты машинного эксперимента по решению одного типа задач теории расписаний методом ветвей и границ и методом вектора спада
Повний текст публікації
Реферат
Рассматривается задача оптимального обслуживания требований параллельными идентичными приборами. Заданы длительности выполнения требований приборами, а также наложены ограничения на последовательность выполнения требований в виде матрицы отношений. Задача состоит в том, чтобы найти такое расписание, при котором время окончания работы всех приборов было бы минимальным.
Множество допустимых вариантов решения бесконечно. Приводится алгоритм выбора конечного подмножества допустимых вариантов, и доказывается, что при этом оптимальное решение не теряется. На выбранном конечном подмножестве решается задача оптимизации двумя методами: точным методом ветвей и границ и методом локальной оптимизации – методом вектора спада. Сравнение времени и точности решения двумя методами осуществлялось на сгенерированных случайным образом исходных данных. Было сгенерировано и решено 60 задач. Среднее время решения методом ветвей и границ составило 86 секунд, методом вектора спада – 3 секунды. Средняя погрешность решения методом вектора спада составила 2 процента.
2007-04-19