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

Приближенный алгоритм для решения NP - полной задачи теории расписаний

Работа №	60844
Тип работы	Бакалаврская работа
Предмет	информатика
Объем работы	51
Год сдачи	2017
Стоимость	4750 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено	330

Не подходит работа?

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

Содержание

Введение 3
Цель работы 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 экономической точки зрения данные задачи позволяют уменьшить затраты на обслуживание путем оптимизации последовательных операций. Происходит сокращение времени на выполнение указанных работ, что позволяет повысить производительность исполняющей стороны, а также увеличить прибыль за выполненные работы.

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

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

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

ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ

Курсовые Статьи Диплом Рязань

Заключение

В данной работе был реализован приближенный алгоритм решения NP - полной задачи теории расписании и его сравнение с точным методом.
Были проведены эксперименты для более точного сравнение запрограммированных алгоритмов. По их результатам можно сказать, что приближенный алгоритм допускает ошибки при поиске оптимального расписания. При расширении отрезка, на котором выбираются данные требований, наблюдается увеличение количества не совпадающих задач. При каждом увеличении правой границы отрезка число таких экспериментов повышалась на 1-5 задачи.
Также существует зависимость между количеством требований и количеством не совпадающих экспериментов. Можно увидеть, что при каждом увеличении требовании, количество не совпадающих экспериментов повышалось на 6-19. При увеличении количества требований рост задач, у которых различная функция штрафа не совпадало, происходит быстрее, чем при расширении отрезка.
При более подробном рассмотрении экспериментов, у которых функция штрафа обоих алгоритмов не совпало, можно наблюдать, что величина погрешности не превышает половины максимальной продолжительности требований.

Литература

1. Танаев В.С., Шкурба В.В. «Введение в теорию расписаний» - Москва: Наука, 1975. - 258 с.
2. Конвей Р., Масквелл В., Миллер Л. «Теория расписаний» - Москва: Наука, 1975. - 360 с.
3. Экель. Б. «Философия Java. Библиотека программиста.» - СПб.: Питер, 2009. - 640 с.
4. Шульгина О. Н. Общая схема решения одной NP - трудной в сильном смысле задачи теории расписаний // Журн. Автоматика и телемеханика. - 2004. - 108 - 116 с.