📄Работа №61721
Тема: Сравнение приближенных методов решения задачи минимизации максимального временного смещения
Тип работы
Бакалаврская работа
Предмет
Информатика и вычислительная техника
Объем:
40 листов
Год:
2017
Просмотров:
338
4750
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение
1.Цель работы
2.1. Первый приближенный алгоритм
2.2. Второй приближенный алгоритм .
3. Описание работы проекта
4. Анализ экспериментов
Заключение
Список использованной литературы
Приложение
1.Цель работы
2.1. Первый приближенный алгоритм
2.2. Второй приближенный алгоритм .
3. Описание работы проекта
4. Анализ экспериментов
Заключение
Список использованной литературы
Приложение
📖 Введение
На протяжении всей жизни мы сталкиваемся с различными расписаниями: расписанием учебных занятий, транспорта, телевизионных передач. Каждый из нас составляет разумное на его взгляд расписание выполнения повседневных работ. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточным. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение. Так как лучше равномерно подготовиться к 3-м экзаменам и получить три четверки, чем неравномерно и получить две пятерки и тройку - можно не получить стипендию.
Многие задачи планирования и управления требуют упорядочения во времени фиксированной системы ресурсов для выполнения определенной совокупности работ. От выбора постановки и качества решения таких задач существенно зависит рациональная организация работ и эффективность производства.
Начиная с пятидесятых годов, задачи календарного планирования и оперативного управления привлекают внимание специалистов по исследованию операций. В связи с большим разнообразием анализируемых ситуаций исследования группировались по различным характерным признакам и проводились в рамках различных научных дисциплин. В теории сетевого планирования основное внимание уделялось распределению времени и материальных ресурсов при выполнении заданного комплекса работ. В теории расписаний рассматривались неделимые виды ресурсов (станки, машины) и такие виды работ, как операции по обработке и транспортировке некоторых деталей, изделий, продуктов. В теории массового
обслуживания рассматривались задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами, приборами. Формальные модели, отвечающие разнообразным по постановке и содержанию задачам календарного планирования и оперативного управления, обнаруживают определенное сходство. Для их анализа могут быть использованы и однотипные математические методы [2, стр.7].
Задачи составления расписаний возникают в частности:
• на производстве, когда нужно упорядочить отдельные операции по исполнителям (цеха, станки) и по времени;
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей; • при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации.
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом . Подавляющее большинство исследованных задач теории расписаний
Л
являются NP-полными . Несмотря на это, практика требует решения таких задач. Для этого существует несколько подходов. Первым подходом является
-5
разработка полиномиальных эвристических алгоритмов . Для некоторых
эвристических алгоритмов известны оценки погрешности получаемого решения. Такие алгоритмы называются приближенными. [1, стр.10]
В настоящий момент широкое распространение имеют мета эвристические алгоритмы, которые находят “хорошее” решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. Неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-полными, т.е. алгоритмы их решения, реализованные на ЭВМ, могут требовать неприемлемо большое время работы для решения практических задач “большой размерности”.
Многие задачи планирования и управления требуют упорядочения во времени фиксированной системы ресурсов для выполнения определенной совокупности работ. От выбора постановки и качества решения таких задач существенно зависит рациональная организация работ и эффективность производства.
Начиная с пятидесятых годов, задачи календарного планирования и оперативного управления привлекают внимание специалистов по исследованию операций. В связи с большим разнообразием анализируемых ситуаций исследования группировались по различным характерным признакам и проводились в рамках различных научных дисциплин. В теории сетевого планирования основное внимание уделялось распределению времени и материальных ресурсов при выполнении заданного комплекса работ. В теории расписаний рассматривались неделимые виды ресурсов (станки, машины) и такие виды работ, как операции по обработке и транспортировке некоторых деталей, изделий, продуктов. В теории массового
обслуживания рассматривались задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами, приборами. Формальные модели, отвечающие разнообразным по постановке и содержанию задачам календарного планирования и оперативного управления, обнаруживают определенное сходство. Для их анализа могут быть использованы и однотипные математические методы [2, стр.7].
Задачи составления расписаний возникают в частности:
• на производстве, когда нужно упорядочить отдельные операции по исполнителям (цеха, станки) и по времени;
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей; • при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации.
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом . Подавляющее большинство исследованных задач теории расписаний
Л
являются NP-полными . Несмотря на это, практика требует решения таких задач. Для этого существует несколько подходов. Первым подходом является
-5
разработка полиномиальных эвристических алгоритмов . Для некоторых
эвристических алгоритмов известны оценки погрешности получаемого решения. Такие алгоритмы называются приближенными. [1, стр.10]
В настоящий момент широкое распространение имеют мета эвристические алгоритмы, которые находят “хорошее” решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. Неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-полными, т.е. алгоритмы их решения, реализованные на ЭВМ, могут требовать неприемлемо большое время работы для решения практических задач “большой размерности”.
✅ Заключение
В процессе выполнения дипломной работы были изучены методы решения задачи теории расписаний для одного прибора, в частности, задачи минимизации максимального временного смещения. Также была продумана структура каждого метода решения задачи теории расписаний, были изучены архитектура и синтаксис языка программирования Python. Сложностей при этом не возникло, так как все изучалось и проектировалось постепенно и согласованно с научным руководителем. После изучения теоретической и практической частей был спроектировано приложение с очень простым на вид и не сложным в применении интерфейсом.
Программный код содержит 3 метода решения задачи теории расписаний, результаты которых были сравнены. Проводилось несколько экспериментов, сравнивая решения каждого метода при определенном количестве требований и генераций, а также с различными комбинациями чисел. Исследования имеют следующие результаты:
- и при 3, и при 5, и при 7 требованиях алгоритм 1 построил больше оптимальных расписаний, чем алгоритм 2, значит, алгоритм 1 наиболее близок к методу полного перебора, в отличие от алгоритма 2;
- отношение между значениями целевой функцией расписания алгоритмов 1 и 2 и оптимального расписания примерно одинаково.
- исследования генераций с 8 и 9 требованиями показали, что ни один приближенный алгоритм не построил оптимального расписания.
Из этого всего следует, что при увеличении числа требований, количество оптимальных расписаний уменьшается. Алгоритм 1 более точен, чем алгоритм 2.
Программный код содержит 3 метода решения задачи теории расписаний, результаты которых были сравнены. Проводилось несколько экспериментов, сравнивая решения каждого метода при определенном количестве требований и генераций, а также с различными комбинациями чисел. Исследования имеют следующие результаты:
- и при 3, и при 5, и при 7 требованиях алгоритм 1 построил больше оптимальных расписаний, чем алгоритм 2, значит, алгоритм 1 наиболее близок к методу полного перебора, в отличие от алгоритма 2;
- отношение между значениями целевой функцией расписания алгоритмов 1 и 2 и оптимального расписания примерно одинаково.
- исследования генераций с 8 и 9 требованиями показали, что ни один приближенный алгоритм не построил оптимального расписания.
Из этого всего следует, что при увеличении числа требований, количество оптимальных расписаний уменьшается. Алгоритм 1 более точен, чем алгоритм 2.
ИЛИ
Поиск аналога
📕 Список литературы
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.