📄Работа №30653
Тема: Приближенный алгоритм решения одной задачи теории расписаний
Характеристики работы
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
66 листов
Год:
2018
Просмотров:
523
5900
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 2
1. Теоретические аспекты исследования задачи 5
1.1. Постановка задачи 5
1.2. Приближенный и точный алгоритмы 6
2. Реализация программы 9
2.1. Реализация консольного интерфейса 9
2.2. Реализация программной части 14
3. Экспериментальное исследование 33
3.1. Описание экспериментов 33
3.2. Анализ экспериментов 35
Заключение 37
Список литературы 38
Приложение 1
1. Теоретические аспекты исследования задачи 5
1.1. Постановка задачи 5
1.2. Приближенный и точный алгоритмы 6
2. Реализация программы 9
2.1. Реализация консольного интерфейса 9
2.2. Реализация программной части 14
3. Экспериментальное исследование 33
3.1. Описание экспериментов 33
3.2. Анализ экспериментов 35
Заключение 37
Список литературы 38
Приложение 1
📖 Введение
Теория расписаний является одним из разделов исследования операций. Данное направление в науке берет свое начало с известной работы Генри Гантта 1903г. (Gantt H.L.), предложившего то, что сегодня называют диаграммами Гантта, которые встречаются во многих работах по теории расписаний. Методы и алгоритмы решения задач теории расписаний применяются для решения задач комбинаторной оптимизации. С 50-х годов 20-го века началось активное теоретическое исследование задач теории расписаний, следует отметить работы Джонсона, Джексона и Смита, а также монографии.
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона, Ленстры и др., Лоулера и др., Танаева и др., Брукера и др. [1, С.9]
Подавляющее большинство исследованных задач теории расписаний являются NP-трудными. Несмотря на это, практика требует решения таких задач.
Задачам для одного прибор уделяется в рамках теории расписаний особое внимание в силу их тесной связи с классическими задачами из других областей дискретной математики, а также в связи с тем, что одноприборные задачи являются частными случаями и подзадачами более сложных практических задач.
Задачи теории расписаний широко применяются в таких областях, как планирование проектов, организация транспортных потоков, управление производством, ресурсами в вычислительных системах и т.д. Разнообразие методов решения задач теории расписаний, а также большие объемы обработки данных делают особо актуальной проблему построения быстрых и эффективных алгоритмов. Данная работа направлена на исследование точности приближенного алгоритма решения задачи минимизации взвешенного количества запаздывающих требований. Выводы, которые делаются в заключении данной работы дают оценку точности и эффективности работы приближенного алгоритма. Учитывая тот факт, что трудоемкость приближенного алгоритма гораздо меньше, чем точного, такая оценка в целом может быть полезной для оптимизации вычислений в областях, где приоритетом является скорость решения задач, а не точность. В этих случаях практическое применение такого алгоритма может принести значительные экономические выгоды предприятию.
Для указанной задачи достаточные условие оптимальности получены В.С. Танаевым и В.С. Гордоном [3]. В случае одновременного поступления алгоритмы решения разработаны Moore J.M., Kise H., Ibaraki T. и Mine H. в [8]. В случае одновременного поступления при условии возможности нумерации требований одновременно по неубыванию продолжительностей и не возрастанию весов предложен алгоритм В.С. Гордоном и В.С. Танаевым [1]. Решение задачи в случае единичных весов получено Kise H. [5], Maxwell W.I. [7], Lawler E.L. [6], Sidney J.B. [9].
Также полученные данные и выводы могут быть полезными при дальнейшем сравнении алгоритмов такой же трудоемкости, с целью выявления наиболее эффективного среди них алгоритма для данного типа производства и задач, решаемых на нем.
Основными целями данной работы являлись:
1) Разработка программного продукта, позволяющего исследовать задачу минимизации взвешенного количества запаздывающих требований с помощью приближенного и точного алгоритмов, а также обладающего удобным и функциональным диалоговым окном.
2) Исследование задачи минимизации взвешенного количества запаздывающих требований, заключающееся в сравнении результатов приближенного и точного алгоритма и оценке точности приближенного алгоритма
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом и др. Достаточно полные обзоры по задачам теории расписаний и их сложности представлены в работах Гэри и Джонсона, Ленстры и др., Лоулера и др., Танаева и др., Брукера и др. [1, С.9]
Подавляющее большинство исследованных задач теории расписаний являются NP-трудными. Несмотря на это, практика требует решения таких задач.
Задачам для одного прибор уделяется в рамках теории расписаний особое внимание в силу их тесной связи с классическими задачами из других областей дискретной математики, а также в связи с тем, что одноприборные задачи являются частными случаями и подзадачами более сложных практических задач.
Задачи теории расписаний широко применяются в таких областях, как планирование проектов, организация транспортных потоков, управление производством, ресурсами в вычислительных системах и т.д. Разнообразие методов решения задач теории расписаний, а также большие объемы обработки данных делают особо актуальной проблему построения быстрых и эффективных алгоритмов. Данная работа направлена на исследование точности приближенного алгоритма решения задачи минимизации взвешенного количества запаздывающих требований. Выводы, которые делаются в заключении данной работы дают оценку точности и эффективности работы приближенного алгоритма. Учитывая тот факт, что трудоемкость приближенного алгоритма гораздо меньше, чем точного, такая оценка в целом может быть полезной для оптимизации вычислений в областях, где приоритетом является скорость решения задач, а не точность. В этих случаях практическое применение такого алгоритма может принести значительные экономические выгоды предприятию.
Для указанной задачи достаточные условие оптимальности получены В.С. Танаевым и В.С. Гордоном [3]. В случае одновременного поступления алгоритмы решения разработаны Moore J.M., Kise H., Ibaraki T. и Mine H. в [8]. В случае одновременного поступления при условии возможности нумерации требований одновременно по неубыванию продолжительностей и не возрастанию весов предложен алгоритм В.С. Гордоном и В.С. Танаевым [1]. Решение задачи в случае единичных весов получено Kise H. [5], Maxwell W.I. [7], Lawler E.L. [6], Sidney J.B. [9].
Также полученные данные и выводы могут быть полезными при дальнейшем сравнении алгоритмов такой же трудоемкости, с целью выявления наиболее эффективного среди них алгоритма для данного типа производства и задач, решаемых на нем.
Основными целями данной работы являлись:
1) Разработка программного продукта, позволяющего исследовать задачу минимизации взвешенного количества запаздывающих требований с помощью приближенного и точного алгоритмов, а также обладающего удобным и функциональным диалоговым окном.
2) Исследование задачи минимизации взвешенного количества запаздывающих требований, заключающееся в сравнении результатов приближенного и точного алгоритма и оценке точности приближенного алгоритма
✅ Заключение
В процессе написания дипломного проекта была проделана работа в 3 этапа:
1. Изучение теоретических аспектов задачи минимизации взвешенного количества запаздывающих требований.
2. Реализация точного алгоритма и приближенного алгоритма с двумя модификациями в программном проекте.
3. Осуществление экспериментальных исследований и анализ полученных результатов.
Исходя из результатов исследования и анализа алгоритмов, можно сделать вывод, что при небольшом количестве требований лучше использовать второй метод. Значение его целевой функции часто совпадало с оптимальным значением, а если не совпадало, то не сильно от него отличалось (большинство неоптимальных решений попадают в первую группу). Однако при большом количестве требований второй метод сильно уступает первому методу, причем, когда требований становится больше 50 целевая функция второго метода всегда больше целевой функции первого.
1. Изучение теоретических аспектов задачи минимизации взвешенного количества запаздывающих требований.
2. Реализация точного алгоритма и приближенного алгоритма с двумя модификациями в программном проекте.
3. Осуществление экспериментальных исследований и анализ полученных результатов.
Исходя из результатов исследования и анализа алгоритмов, можно сделать вывод, что при небольшом количестве требований лучше использовать второй метод. Значение его целевой функции часто совпадало с оптимальным значением, а если не совпадало, то не сильно от него отличалось (большинство неоптимальных решений попадают в первую группу). Однако при большом количестве требований второй метод сильно уступает первому методу, причем, когда требований становится больше 50 целевая функция второго метода всегда больше целевой функции первого.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.