Введение 4
Глава 1. Постановка задачи 5
Глава 2. Аппроксимационные алгоритмы с гарантированной оценкой точности 6
2.1. Основные определения 6
2.2. Расширенное правило Джексона 7
2.3. Алгоритм H 8
Глава 3. Вычислительные эксперименты и результаты ... 11
3.1. Генерация тестовой выборки 11
3.2. Вычисление оптимального решения 12
3.3. Результаты вычислений 12
Заключение 21
Список литературы 22
Приложение А. Generate samples 23
В данной работе рассматривается задача составления расписания на одном процессоре, где каждая работа имеет время выпуска, время обработки и время доставки. Прерывания во время обработки запрещены. Каждая работа должна начинать свое выполнение не раньше момента наступления. Процесс доставки начинается сразу после завершения выполнения.
Целью является минимизация максимального времени завершения всех работ.
Данная задача является ЖР-трудной, в связи с чем актуальным становится применение приближенных алгоритмов.
В главе 1 приводится формальная постановка задачи.
В главе 2 рассматриваются аппроксимационные алгоритмы с гарантированной оценкой точности, а также вводятся основные понятия, необходимые для их понимания.
В главе 3 представлены результаты вычислительных экспериментов.
Основной целью работы является реализация приближенных алгоритмов с гарантированной оценкой точности, проведение численных экспериментов, а также анализ полученных результатов.
В данной работе были рассмотрены аппроксимационные алгоритмы с гарантированной оценкой точности для задачи с заданными параметрами работ:
- время выпуска, г«;
- время обработки, рд
- время доставки, щ.
Реализованы программы представленных в работе алгоритмов, а также программа для генерации тестовых примеров.
Вычислительные эксперименты показали, что при увеличении диапазона генерируемых времен доставки, доля совпадающих с оптимальным решением результатов рассматриваемых алгоритмов, уменьшается. Также стоит отметить, что в большей части тестовых примеров аппроксимационные алгоритмы дают решение, близкое к оптимальному.
Все результаты получены с помощью программы, с которой можно ознакомиться по ссылке https://yadi.sk/d/pstEP6aB3JRUdY/2017.
