Тема: ИССЛЕДОВАНИЕ АЛГОРИТМА РЕШЕНИЯ NP-ПОЛНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ

Теория расписаний - это один из разделов исследований операций, который связан с построением математических моделей календарного планирования, то есть с упорядочиванием некоторых работ по времени и (или) по исполнителям. Целью решения задач теории расписаний является поиск расписания с наилучшим значением заданной целевой функции, при котором соблюдены все ограничения. Это большой круг задач, которые имеют обширное применение везде, где возникает возможность выбора порядка выполнения работ: в организации производства и транспортных перевозок, в оптимизации компьютерных вычислений, в бизнесе и во многих других областях человеческой деятельности. Поэтому вопросы составления наилучшего расписания являются актуальными.
Существует большое количество задач теории расписаний, требующих решения, многие из которых является NP-трудными, и реализация составления оптимального расписания требует больших временных затрат. Для многих из них нет необходимости в точном ответе, достаточно построить разумное решение за короткое время. Поэтому разработка эффективных приближенных алгоритмов с оценкой абсолютной погрешности для NP-трудных задач является одним из важных и актуальных направлений исследований.
В выпускной квалификационной работе исследуются два приближенных алгоритма решения NP-трудного частного случая задачи теории расписаний - минимизации максимального временного смещения для одного прибора, когда требования можно перенумеровать одновременно по неубыванию директивных сроков и невозрастанию моментов поступления. Делается выбор в пользу одного из алгоритмов.
В первой главе раскрываются теоретические и методологические основы изучения проблемы: ставится задача, предлагаются методы ее решения и определяется цель исследования.
Вторая глава посвящена описанию программного проекта: реализации алгоритмов и разработке пользовательского интерфейса, а также демонстрации работы программы.
В третьей главе проводятся экспериментальные исследования и анализ полученных результатов, устанавливается зависимость результатов от входных данных.

Купить

В ходе выпускной квалификационной работы были реализованы два приближенных алгоритма решения частного случая задачи теории расписаний - минимизации максимального временного смещения, и разработан удобный для исследования данных методов интерфейс.
Было проведено экспериментальное сравнение двух алгоритмов, один из которых является модификацией другого с меньшей на порядок трудоемкостью его реализации. В ходе серии экспериментов было выявлено, что методы не всегда дают одинаковый результат, при этом в случае несовпадения первый алгоритм строит расписание с меньшим значением целевой функции. Была установлена зависимость количества несовпадений от количества требований: чем больше требований, тем реже встречаются несовпадения при одинаковых диапазонах генерации параметров требований. При этом, чем больше диапазон, тем чаще возникают несовпадения. Также выяснилось, что разница между значениями целевой функции расписаний, построенных первым и вторым алгоритмами, в случае несовпадения результатов является незначительной при заданных параметрах требований.
В связи с этим можно сделать вывод, что использование второго алгоритма более эффективно, так как он является менее трудоемким по сравнению с первым. Так как методы являются вспомогательными, использование второго алгоритма позволит уменьшить трудоемкость реализации точного метода.

Купить