Тип работы:
Предмет:
Язык работы:


Разработка и исследование алгоритмов решения задачи минимизации максимального временного смещения

Работа №32496

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы74
Год сдачи2018
Стоимость4900 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
408
Не подходит работа?

Узнай цену на написание


ВВЕДЕНИЕ 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
ПРИЛОЖЕНИЕ

На протяжении всей жизни люди сталкиваются с проблемой планирования своего времени. Например, мы знаем, какие дела нам нужно сделать сегодня и оцениваем, сколько на эти действия уйдет времени. Исходя из этих данных, мы строим план действий, то есть составляем некое расписание. Чаще всего составление расписания не составляет трудности для человека и, в основном все мы придерживаемся “похожими действиями”, то есть интуитивно мы понимаем, что и когда нам нужно сделать, чтобы сделать все дела вовремя. Возьмем конкретный пример того, как студенты готовятся к сдаче экзаменов. Например, одному студенту нужно сдать 3 экзамена с 3 днями на подготовку к каждому. Для получения положительного результата, в данном случае для получения стипендии, он не будет готовиться к первому экзамену, уча материал по третьему и наоборот. Таким образом, большинство студентов составят такое расписание: “первые три дня готовлюсь к первому экзамену, следующие 3 дня ко второму и последние три дня к третьему”.
Вся сложность появляется тогда, когда необходимо составить расписание, где нужно учесть множество дополнительных факторов и нюансов или, например, составить расписания не для одного человека, а для группы людей, в которой нужно учесть интересы каждого. Представьте себе сотни работ и десятки исполнителей, для которых необходимо составить расписание. Именно в таких случаях и появляется необходимость в изучении основ такой науки как теория расписания.
Отдельная наука теория расписания начала формироваться еще в середине 20 века с исследований Д.Х.Джексона[1] и Д.П.Джонсона[2]. Примерно в это время начинают формироваться новые области математики - теория многокритериального принятия решений, теория массового обслуживания, теория автоматического управления, теория оптимального управления и т.п.
Модели, изучаемые в теории расписаний, возникают во многих сферах человеческой деятельности: образовании, транспорте, при календарном планировании производства, управлении, информатике, сельском хозяйстве и т.д.
Таким образом, задачи теории расписания упорядочивают некоторые работы по времени или по исполнителям. Цель решения таких задач - построение допустимого расписания, при котором соблюдены все ограничения или найдено решение, удовлетворяющее тому или иному критерию оптимальности.
Практически все задачи теории расписания являются NP- полными, то есть это такие задачи, которые нельзя решить никаким известным полиномиальным алгоритмом и для решения подобных задач затрачивается много ресурсов и временных затрат. Поэтому исследование свойств оптимальных расписаний и построение на их основе эффективных приближенных алгоритмов, а также точных алгоритмов решения частных случаев задач являются актуальными проблемами теории расписаний. Чем мы и займемся в данной работе.


Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!


Для NP-полной задачи теории расписаний - минимизации максимального временного смещения проведено экспериментальное сравнение результатов работы приближенных алгоритмов.
Для проведения указанного исследования были выполнены следующие работы:
• Изучены метод ветвей и границ и приближенные алгоритмы.
• Все алгоритмы были запрограммированы.
• Разработан удобный интерфейс для использования приложения.
• Проведено множество экспериментов над работой алгоритмов.
• Проведен анализ полученных результатов.
По анализу результатов можно сделать вывод, что приближенный алгоритм 1 выдает оптимальный результат при поступлении примера с невозрастанием моментов поступления и неубыванием директивных сроков и наоборот. Приближенный алгоритм 2 показывает обратное. Кроме случая с неубыванием моментов поступления и невозрастанием директивных сроков алгоритм выдает близкие к оптимальным результаты. При случайных поступлениях требований оба алгоритма показывают средние показатели построения оптимального расписания. В среднем для 80-85% примеров приближенные алгоритмы выдают оптимальное решение.



1. Джексон Дж.Р. , Планирование производственной линии для минимизации максимальной задержки / / Лос-Анджелес, Калифорния: Калифорнийский Университет, 1955.
2. Джонсон С.М., Оптимальные двух-и трехступенчатые графики производства с учетом времени наладки. // Ежеквартальные Морские Исследования Логистики, 1954. Стр. 61-68.
3. Шульгина О. Н., Щербакова Н. К. Псевдополиномиальный приближенный алгоритм решения NP-полной задачи минимизации максимального временного смещения - Казань, 2008.
4. Гант Г.Л. Операции по ASME, 1903. Стр. 1322-1336.
5. Беллман Р. Математические аспекты теории расписания // Журнал общества промышленной и прикладной математики, 1956. Стр. 168205.
6. Беллман Р. Динамическое программирование М.: ИЛ, 1960. 400 с.
7. Левин В.И., Задача Беллмана - Джонсона для конвейерных систем с переменным порядком работ, 2003. Стр. 1-7.
8. Конвей Р.В., Максвелл В.Л., Миллер Л.В., Теория расписаний//Главная редакция физико-математической литературы - издательство «Наука»,1975.
9. Конвей Р.В., Максвел В.Л, Миллер Л.В., Теория планирования. Аддисон-Уэсли, чтение, Массачусетс, 1967.
10. Танаев В.С., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.
11. Лэнд А.Х., Дойг А.Г. Автоматический метод решения задач дискретного программирования, стр. 497-520.
12. Шульгина О. Н., Щербакова Н. К. Об одном приближенном алгоритме решения NP - трудной задачи теории расписаний// Сборн. иссл. по прикл. матем. - Выпуск 24. - Казань, 2003. - С. 146 - 156.
13. Шульгина О. Н. Процедура построения допустимого расписания для задачи минимизации максимального временного смещения // Исслед. по прикл. матем. - Выпуск 23. - Казань,2001 - С. 150 - 158.
14. Шульгина О. Н. Точный псевдополиномиальный алгоритм решения одной NP-трудной задачи теории расписаний// Сборн. иссл. по прикл. матем. и информатике.— Вып. 25.— Казань, 2004.— С. 148—151.
15. Шульгин А. В. Разработка и исследование алгоритма решения одной задачи теории расписаний/ Физико-математические науки// Национальная ассоциация ученых, ежемесячный научный журнал. Выпуск 22, г.Екатеринбург, 2016. Стр. 10-11.
16. Бланшет Ж., Саммерфилд М., Qt4 Программирование GUI на С++. 2ed. - 2008.
17. Грехем Р.Л., Ленстра Д.К., Ринна Кан А.Х.Г. Оптимизация и аппроксимация в детерминированном планировании: обзор / / летописи дискретной математики, 1979. Стр. 287-326.
18. Лазарев А. А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации - Москва, 2007. - С. 426.
19. Лазарев А.А., Гафаров Е. Р. Теория расписаний, задачи и алгоритмы. - Москва,2011. - С. 222.


Работу высылаем на протяжении 30 минут после оплаты.



Подобные работы


©2024 Cервис помощи студентам в выполнении работ