Тема: Приближенный алгоритм для решения NP - полной задачи теории расписаний
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
📋 Содержание
Цель работы 4
Глава 1. Изложение и разработка алгоритма 5
1.1. Общие понятия, определения 5
1.2. Приближенный алгоритм для решения NP - полной задачи теории
расписаний 6
1.3. Метод перебора 7
Глава 2. Реализация алгоритма 8
2.1. Вспомогательные функции 9
2.1.1. Хранение исходных данных 9
2.1.2. Генерация исходных данных 9
2.1.3. Функция для печати данных 10
2.1.4. Функция для подсчета штрафа и время завершения расписания 10
2.1.5. Функция для перенумерации требований 10
2.2. Программный комплекс 11
2.2.1. Главное окно 11
2.2.2. Окно для ввода данных с консоли 12
2.2.3. Окно для генерации случайных данных 12
2.3. Сравнение алгоритмов 12
2.3.1. 3 требования 12
2.3.2. 4 требования 15
2.3.3. 6 требований 17
2.3.4. 8 требований 19
2.3.5. 10 требований 22
2.4. Демонстрация работы программы 25
Заключение 28
Список использованной литературы 29
Приложение
📖 Введение
Задачи теории расписаний применяются в таких предметных областях как управление производством, организация транспортных потоков, планирование проектов, управление ресурсами в вычислительных системах[1].
Разработанная программа, позволяющая в автоматизированном режиме составлять оптимальное расписание либо близкое к оптимальному за приемлемое время, например, для производства множества видов изделий на множестве станков с разными видами работ, является актуальной.
C экономической точки зрения данные задачи позволяют уменьшить затраты на обслуживание путем оптимизации последовательных операций. Происходит сокращение времени на выполнение указанных работ, что позволяет повысить производительность исполняющей стороны, а также увеличить прибыль за выполненные работы.
✅ Заключение
Были проведены эксперименты для более точного сравнение запрограммированных алгоритмов. По их результатам можно сказать, что приближенный алгоритм допускает ошибки при поиске оптимального расписания. При расширении отрезка, на котором выбираются данные требований, наблюдается увеличение количества не совпадающих задач. При каждом увеличении правой границы отрезка число таких экспериментов повышалась на 1-5 задачи.
Также существует зависимость между количеством требований и количеством не совпадающих экспериментов. Можно увидеть, что при каждом увеличении требовании, количество не совпадающих экспериментов повышалось на 6-19. При увеличении количества требований рост задач, у которых различная функция штрафа не совпадало, происходит быстрее, чем при расширении отрезка.
При более подробном рассмотрении экспериментов, у которых функция штрафа обоих алгоритмов не совпало, можно наблюдать, что величина погрешности не превышает половины максимальной продолжительности требований.