Введение 3
1. Цель и задача исследования 5
1.1. Постановка задачи и обозначения 5
1.2. Методы решения задачи 7
1.2.1. Процедура ho 7
1.2.2. Модификация процедуры h0 8
1.3. Цель работы 9
2. Программная реализация 10
2.1. Реализация методов и интерфейса 10
2.2. Демонстрация работы программы 15
3. Экспериментальные исследования 30
3.1. Описание экспериментальных исследований 30
3.2. Анализ результатов экспериментальных исследований 32
Заключение 34
Список использованных источников 35
Приложения
Купить

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

Купить