Введение
1.Цель работы
2.1. Первый приближенный алгоритм
2.2. Второй приближенный алгоритм .
3. Описание работы проекта
4. Анализ экспериментов
Заключение
Список использованной литературы
Приложение
На протяжении всей жизни мы сталкиваемся с различными расписаниями: расписанием учебных занятий, транспорта, телевизионных передач. Каждый из нас составляет разумное на его взгляд расписание выполнения повседневных работ. Для решения бытовых вопросов применение интуитивного подхода оказывается достаточным. Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение. Так как лучше равномерно подготовиться к 3-м экзаменам и получить три четверки, чем неравномерно и получить две пятерки и тройку - можно не получить стипендию.
Многие задачи планирования и управления требуют упорядочения во времени фиксированной системы ресурсов для выполнения определенной совокупности работ. От выбора постановки и качества решения таких задач существенно зависит рациональная организация работ и эффективность производства.
Начиная с пятидесятых годов, задачи календарного планирования и оперативного управления привлекают внимание специалистов по исследованию операций. В связи с большим разнообразием анализируемых ситуаций исследования группировались по различным характерным признакам и проводились в рамках различных научных дисциплин. В теории сетевого планирования основное внимание уделялось распределению времени и материальных ресурсов при выполнении заданного комплекса работ. В теории расписаний рассматривались неделимые виды ресурсов (станки, машины) и такие виды работ, как операции по обработке и транспортировке некоторых деталей, изделий, продуктов. В теории массового
обслуживания рассматривались задачи назначения приоритетов в обслуживании поступающих заявок некоторыми устройствами, приборами. Формальные модели, отвечающие разнообразным по постановке и содержанию задачам календарного планирования и оперативного управления, обнаруживают определенное сходство. Для их анализа могут быть использованы и однотипные математические методы [2, стр.7].
Задачи составления расписаний возникают в частности:
• на производстве, когда нужно упорядочить отдельные операции по исполнителям (цеха, станки) и по времени;
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей; • при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации.
Одним из главных вопросов нового направления была классификация задач и установление их сложности. Наиболее устоявшаяся на нынешний день классификация задач теории расписаний была предложена Грэхэмом . Подавляющее большинство исследованных задач теории расписаний
Л
являются NP-полными . Несмотря на это, практика требует решения таких задач. Для этого существует несколько подходов. Первым подходом является
-5
разработка полиномиальных эвристических алгоритмов . Для некоторых
эвристических алгоритмов известны оценки погрешности получаемого решения. Такие алгоритмы называются приближенными. [1, стр.10]
В настоящий момент широкое распространение имеют мета эвристические алгоритмы, которые находят “хорошее” решение, близкое к оптимальному, за приемлемое время. Недостатком таких алгоритмов является отсутствие оценок качества полученного решения. Неизвестно, насколько решение отличается от оптимального в наихудшем случае.
Решение задач теории расписаний усложняется тем фактом, что большинство из них являются NP-полными, т.е. алгоритмы их решения, реализованные на ЭВМ, могут требовать неприемлемо большое время работы для решения практических задач “большой размерности”.
В процессе выполнения дипломной работы были изучены методы решения задачи теории расписаний для одного прибора, в частности, задачи минимизации максимального временного смещения. Также была продумана структура каждого метода решения задачи теории расписаний, были изучены архитектура и синтаксис языка программирования Python. Сложностей при этом не возникло, так как все изучалось и проектировалось постепенно и согласованно с научным руководителем. После изучения теоретической и практической частей был спроектировано приложение с очень простым на вид и не сложным в применении интерфейсом.
Программный код содержит 3 метода решения задачи теории расписаний, результаты которых были сравнены. Проводилось несколько экспериментов, сравнивая решения каждого метода при определенном количестве требований и генераций, а также с различными комбинациями чисел. Исследования имеют следующие результаты:
- и при 3, и при 5, и при 7 требованиях алгоритм 1 построил больше оптимальных расписаний, чем алгоритм 2, значит, алгоритм 1 наиболее близок к методу полного перебора, в отличие от алгоритма 2;
- отношение между значениями целевой функцией расписания алгоритмов 1 и 2 и оптимального расписания примерно одинаково.
- исследования генераций с 8 и 9 требованиями показали, что ни один приближенный алгоритм не построил оптимального расписания.
Из этого всего следует, что при увеличении числа требований, количество оптимальных расписаний уменьшается. Алгоритм 1 более точен, чем алгоритм 2.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
