ВВЕДЕНИЕ 5
Глава 1 ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ
ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ 7
1.1 Задачи дискретной оптимизации 7
1.2 Метод ветвей и границ 8
Глава 2 ФОРМАЛИЗАЦИЯ КОНВЕЙЕРНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ 16
2.1 Постановка конвейерной задачи теории расписаний 16
2.2 Математическое моделирование конвейерной задачи 18
Глава 3 АЛГОРИТМ ВЕТВЕЙ И ГРАНИЦ ДЛЯ РЕШЕНИЯ
КОНВЕЙЕРНОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ 24
3.1 Алгоритм ветвей и границ для решения задачи Джонсона для двух
станков 24
3.2 Реализация алгоритма ветвей и границ для решения конвейерной задачи
теории расписания 31
ЗАКЛЮЧЕНИЕ 41
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 42
ПРИЛОЖЕНИЕ А Фрагмент программного кода приложения
В настоящее время для управления социально-экономическими системами и производственными объектами применяются прикладные задачи, относящиеся к категории задач теории расписаний.
Как правило, на основе методов теории расписаний решаются задачи производственного календарного и сетевого планирования, а также управления проектами.
Среди вышеперечисленных задач особо следует выделить задачи так называемых конвейерных расписаний, в которых порядок выполнения операций для каждого задания одинаков.
Для решения задач оптимизации конвейерных расписаний теории расписаний используются различные методы, среди которых наибольший научно-практический интерес представляет метод ветвей и границ.
Таким образом, актуальность бакалаврской работы обусловлена необходимостью решения задач конвейерных расписаний с помощью метода ветвей и границ.
Объектом исследования бакалаврской работы является конвейерная задача теории расписаний.
Предмет исследования бакалаврской работы - метод ветвей и границ для конвейерной задачи теории расписаний.
Целью бакалаврской работы является анализ и применение метода ветвей и границ для решения конвейерной задачи теории расписаний.
Для достижения поставленной цели необходимо решить следующие задачи:
- проанализировать научную и учебно-методическую литературу по теме бакалаврской работы;
- описать метод ветвей и границ решения конвейерной задачи теории расписаний;
- формализовать конвейерную задачу теории расписаний;
- произвести анализ и представить пример применения алгоритма метода ветвей и границ для решения конвейерной задачи теории расписаний.
Методы исследования: теория расписаний, метод ветвей и границ.
Практическая значимость бакалаврской работы заключается в практическом применении алгоритмов метода ветвей и границ для решения конвейерной задачи теории расписаний.
Первая глава посвящена проблеме применения метода ветвей и границ для решения задач дискретной оптимизации. Описаны принципы метода ветвей и границ.
Во второй главе рассматривается формализация конвейерной задачи теории расписаний. Выполнена постановка задачи и описана математическая модель конвейерной задачи теории расписаний.
В третьей главе исследованы алгоритмы ветвей и границ для решения конвейерной задачи теории расписаний. Разработана и протестирована программа реализации алгоритма решения конвейерной задачи.
В заключении подводятся итоги исследования, формируются окончательные выводы по исследуемой проблемы.
В приложении представлен фрагмент программного кода.
Бакалаврская работа состоит из 46 страниц и включает 6 рисунков, 16 таблиц, 24 источника.
Представленная бакалаврская работа посвящена актуальной проблеме применения метода ветвей и границ для решения конвейерной задачи теории расписаний.
В ходе выполнения бакалаврской работы достигнуты следующие результаты:
1) проанализирована научная и учебно-методическая литература по исследуемой проблеме;
2) описаны принципы метода ветвей и границ решения конвейерной задачи теории расписаний. Как показал анализ, преимуществами метода ВиГ являются обобщенность, адаптивность и применение для решения широкого круга задач дискретной оптимизации, в том числе, для решения конвейерной задачи теории расписания;
3) формализована конвейерная задача теории расписаний для решения с помощью метода ветвей и границ. Анализ известных методов формализации показал, что с помощью булевых переменных и введенных ограничений типовая конвейерная задача теории расписаний может быть сведена к задаче дискретной оптимизации;
4) произведен анализ алгоритма метода ветвей и границ для решения конвейерной задачи теории расписаний и представлен пример его применения для решения задачи Джонсона. Для реализации алгоритма разработана программа на основе специализированного онлайн-сервиса и технологии Electron. Результат решения задачи Джонсона на данной программе совпал с результатом решения c помощью классического алгоритма Джонсона, что подтверждает правильность используемого программного кода алгоритма, основанного на методе ветвей и границ.
Результаты бакалаврской работы могут быть рекомендованы для разработки математического обеспечения систем производственного календарного и сетевого планирования и управления различными проектами.
