Введение 3
1. Теоретические аспекты исследования задачи 5
1.1. Математическая постановка задачи 5
1.2. Метод решения задачи 6
2. Реализация программы 9
2.1. Описания работы программы 9
2.2. Реализация программной части 16
3. Экспериментальное исследование 20
3.1. Описание экспериментов 20
3.2. Анализ эксперимента 21
Заключение 23
Список литературы 25
Приложение
Купить

Теория расписаний - одна из самых популярных разделов исследования операций. В задачи теории расписаний входит упорядочивание некоторых требований (работ) по времени и/или приборам (исполнителям). При этом требуется учитывать ограничения, связанные с временем поступления и временем выполнения требований, а также ограничения, связанные с приборами, например, время начала их работы. Целью решения таких задач является построение допустимых расписаний с соблюдением всех ограничений. Более сложным является нахождение оптимального допустимого расписания по тому или иному критерию оптимальности (например, по быстродействию).
В рамках данной работы изучался метод решения задачи минимизации максимального временного смещения. При нахождении оптимального расписания по данному критерию важную роль играют директивные сроки требований. Директивным сроком называется момент времени, к которому необходимо или, во всяком случае, желательно завершить обслуживание требования. В общем случае не удается построить такого расписания, при котором обслуживание каждого требования завершается не позднее заданного директивного срока. Появляется объективная необходимость в нарушении отдельных директивных сроков, что связано с определенными потерями. Эти потери, как правило, зависят от того, какие именно требования и на сколько задерживаются с обслуживанием [2, с.73].
Большинство задач теории расписаний являются NP-трудными. В настоящее время поиск точных алгоритмов для их решения представляется бесперспективным, так как время их работы ограничено полиномом от размера входа задачи. Алгоритмы переборного типа, даже при решении примеров средней размерности, требуют больших вычислительных затрат. Именно поэтому построение и анализ приближенных алгоритмов является одной из важных направлений исследования. Более того, для многих оптимизационных задач теории расписаний необязательно находить точные ответы. Достаточно построить разумное приблизительное решение за короткое время, с чем успешно справляются приближенные алгоритмы.
Цели данной работы:
1) Программная реализация приближенного метода решения задачи минимизации максимального временного смещения. Программа должна помогать в исследовании данной задачи, а также обладать удобным и понятным для пользователя интерфейсом.
2) Исследование задачи минимизации максимального временного смещения и сравнение результатов приближенных алгоритмов для их решения.
Для разработки программы использовался язык программирования C# и технология WPF (Windows Presentation Foundation). Программа рассчитывает приближенное оптимальное расписание для введенных начальных данных и ограничений. Данные могут быть введены с экрана, а также получены из файла.

Купить