📄Работа №32496
Тема: Разработка и исследование алгоритмов решения задачи минимизации максимального временного смещения
Характеристики работы
Тип работы
Магистерская диссертация
Предмет
Информатика и вычислительная техника
Объем:
74 листов
Год:
2018
Просмотров:
555
4900
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
1. ЦЕЛЬ ИССЛЕДОВАНИЯ 5
2. ОБЩИЕ СВЕДЕНИЯ О ТЕОРИИ РАСПИСАНИЙ 6
2.1 Возникновение и этапы развития теории расписания 6
2.2 Предмет теории расписаний 8
2.3 Способы представления расписаний 9
2.4 Классификация задач теории расписаний 10
2.5 Дополнительные параметры в задачах теории расписаний 12
3. АЛГОРИТМЫ. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 13
3.1 Постановка задачи 15
3.2 Метод ветвей и границ 15
3.3 Приближенный алгоритм 1 15
3.4 Приближенный алгоритм 2 18
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ПРОЕКТА 19
4.1 Платформа для реализации 19
4.2 Архитектура приложения 19
4.3 Описание разработанного приложения 19
5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ 32
ЗАКЛЮЧЕНИЕ 55
СПИСОК ЛИТЕРАТУРЫ 55
ПРИЛОЖЕНИЕ
1. ЦЕЛЬ ИССЛЕДОВАНИЯ 5
2. ОБЩИЕ СВЕДЕНИЯ О ТЕОРИИ РАСПИСАНИЙ 6
2.1 Возникновение и этапы развития теории расписания 6
2.2 Предмет теории расписаний 8
2.3 Способы представления расписаний 9
2.4 Классификация задач теории расписаний 10
2.5 Дополнительные параметры в задачах теории расписаний 12
3. АЛГОРИТМЫ. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ 13
3.1 Постановка задачи 15
3.2 Метод ветвей и границ 15
3.3 Приближенный алгоритм 1 15
3.4 Приближенный алгоритм 2 18
4. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ ПРОЕКТА 19
4.1 Платформа для реализации 19
4.2 Архитектура приложения 19
4.3 Описание разработанного приложения 19
5. СРАВНИТЕЛЬНЫЙ АНАЛИЗ 32
ЗАКЛЮЧЕНИЕ 55
СПИСОК ЛИТЕРАТУРЫ 55
ПРИЛОЖЕНИЕ
📖 Введение
На протяжении всей жизни люди сталкиваются с проблемой планирования своего времени. Например, мы знаем, какие дела нам нужно сделать сегодня и оцениваем, сколько на эти действия уйдет времени. Исходя из этих данных, мы строим план действий, то есть составляем некое расписание. Чаще всего составление расписания не составляет трудности для человека и, в основном все мы придерживаемся “похожими действиями”, то есть интуитивно мы понимаем, что и когда нам нужно сделать, чтобы сделать все дела вовремя. Возьмем конкретный пример того, как студенты готовятся к сдаче экзаменов. Например, одному студенту нужно сдать 3 экзамена с 3 днями на подготовку к каждому. Для получения положительного результата, в данном случае для получения стипендии, он не будет готовиться к первому экзамену, уча материал по третьему и наоборот. Таким образом, большинство студентов составят такое расписание: “первые три дня готовлюсь к первому экзамену, следующие 3 дня ко второму и последние три дня к третьему”.
Вся сложность появляется тогда, когда необходимо составить расписание, где нужно учесть множество дополнительных факторов и нюансов или, например, составить расписания не для одного человека, а для группы людей, в которой нужно учесть интересы каждого. Представьте себе сотни работ и десятки исполнителей, для которых необходимо составить расписание. Именно в таких случаях и появляется необходимость в изучении основ такой науки как теория расписания.
Отдельная наука теория расписания начала формироваться еще в середине 20 века с исследований Д.Х.Джексона[1] и Д.П.Джонсона[2]. Примерно в это время начинают формироваться новые области математики - теория многокритериального принятия решений, теория массового обслуживания, теория автоматического управления, теория оптимального управления и т.п.
Модели, изучаемые в теории расписаний, возникают во многих сферах человеческой деятельности: образовании, транспорте, при календарном планировании производства, управлении, информатике, сельском хозяйстве и т.д.
Таким образом, задачи теории расписания упорядочивают некоторые работы по времени или по исполнителям. Цель решения таких задач - построение допустимого расписания, при котором соблюдены все ограничения или найдено решение, удовлетворяющее тому или иному критерию оптимальности.
Практически все задачи теории расписания являются NP- полными, то есть это такие задачи, которые нельзя решить никаким известным полиномиальным алгоритмом и для решения подобных задач затрачивается много ресурсов и временных затрат. Поэтому исследование свойств оптимальных расписаний и построение на их основе эффективных приближенных алгоритмов, а также точных алгоритмов решения частных случаев задач являются актуальными проблемами теории расписаний. Чем мы и займемся в данной работе.
Вся сложность появляется тогда, когда необходимо составить расписание, где нужно учесть множество дополнительных факторов и нюансов или, например, составить расписания не для одного человека, а для группы людей, в которой нужно учесть интересы каждого. Представьте себе сотни работ и десятки исполнителей, для которых необходимо составить расписание. Именно в таких случаях и появляется необходимость в изучении основ такой науки как теория расписания.
Отдельная наука теория расписания начала формироваться еще в середине 20 века с исследований Д.Х.Джексона[1] и Д.П.Джонсона[2]. Примерно в это время начинают формироваться новые области математики - теория многокритериального принятия решений, теория массового обслуживания, теория автоматического управления, теория оптимального управления и т.п.
Модели, изучаемые в теории расписаний, возникают во многих сферах человеческой деятельности: образовании, транспорте, при календарном планировании производства, управлении, информатике, сельском хозяйстве и т.д.
Таким образом, задачи теории расписания упорядочивают некоторые работы по времени или по исполнителям. Цель решения таких задач - построение допустимого расписания, при котором соблюдены все ограничения или найдено решение, удовлетворяющее тому или иному критерию оптимальности.
Практически все задачи теории расписания являются NP- полными, то есть это такие задачи, которые нельзя решить никаким известным полиномиальным алгоритмом и для решения подобных задач затрачивается много ресурсов и временных затрат. Поэтому исследование свойств оптимальных расписаний и построение на их основе эффективных приближенных алгоритмов, а также точных алгоритмов решения частных случаев задач являются актуальными проблемами теории расписаний. Чем мы и займемся в данной работе.
✅ Заключение
Для NP-полной задачи теории расписаний - минимизации максимального временного смещения проведено экспериментальное сравнение результатов работы приближенных алгоритмов.
Для проведения указанного исследования были выполнены следующие работы:
• Изучены метод ветвей и границ и приближенные алгоритмы.
• Все алгоритмы были запрограммированы.
• Разработан удобный интерфейс для использования приложения.
• Проведено множество экспериментов над работой алгоритмов.
• Проведен анализ полученных результатов.
По анализу результатов можно сделать вывод, что приближенный алгоритм 1 выдает оптимальный результат при поступлении примера с невозрастанием моментов поступления и неубыванием директивных сроков и наоборот. Приближенный алгоритм 2 показывает обратное. Кроме случая с неубыванием моментов поступления и невозрастанием директивных сроков алгоритм выдает близкие к оптимальным результаты. При случайных поступлениях требований оба алгоритма показывают средние показатели построения оптимального расписания. В среднем для 80-85% примеров приближенные алгоритмы выдают оптимальное решение.
Для проведения указанного исследования были выполнены следующие работы:
• Изучены метод ветвей и границ и приближенные алгоритмы.
• Все алгоритмы были запрограммированы.
• Разработан удобный интерфейс для использования приложения.
• Проведено множество экспериментов над работой алгоритмов.
• Проведен анализ полученных результатов.
По анализу результатов можно сделать вывод, что приближенный алгоритм 1 выдает оптимальный результат при поступлении примера с невозрастанием моментов поступления и неубыванием директивных сроков и наоборот. Приближенный алгоритм 2 показывает обратное. Кроме случая с неубыванием моментов поступления и невозрастанием директивных сроков алгоритм выдает близкие к оптимальным результаты. При случайных поступлениях требований оба алгоритма показывают средние показатели построения оптимального расписания. В среднем для 80-85% примеров приближенные алгоритмы выдают оптимальное решение.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.