Введение 3
1. Цель работы 5
2. Постановка задачи 6
3. Описание алгоритма 8
4. Описание работы проекта 9
4.1 Результаты работы проекта 9
5. Примеры 13
6. Эксперименты 16
Заключение 23
Список использованной литературы 25
Приложение 26
Люди на протяжении всей своей жизни сталкиваются с необходимостью составления расписаний. Каждый из нас занимается планированием личного времени. Мы знаем что и к какому сроку нужно выполнить, а также имеем представление, сколько времени потребуется на каждое дело. Исходя из этих данных мы составляем расписание, согласуя наши дела по времени. Чаще всего составление личного расписания не вызывает сложности. Практически все люди при этом руководствуются “похожими алгоритмами”, стремясь сделать все дела вовремя.
Часто мы планируем наши действия в порядке возрастания крайних сроков исполнения работ. Например, студенты во время экзаменационной сессии учат предмет с наименьшим директивным сроком (ближайший по дате сдачи экзамен), тем самым они минимизируют максимальное временное смещение.
Но перед обществом стоят и более трудные задачи. Развивающаяся стремительными темпами автоматизация производства и неуклонно увеличивающиеся его масштабы требуют разработки алгоритмов составления расписаний, в которых учтены разнообразные ограничения.
Теория расписаний - одна из самых популярных с теоретической и практической точек зрения области исследования операций. Задачи теории расписаний, разумеется, связаны с построением расписаний, т.е. с упорядочиванием некоторых работ (операций) по времени и/или по исполнителям (приборам). При этом необходимо учитывать ограничения на последовательность выполнения работ, ограничения, связанные с исполнителями, и т.п. Цель решения таких задач - построение допустимых расписаний, при котором все ограничения соблюдены, или, что является более сложным, - нахождение оптимального допустимого расписания потому или иному критерию оптимальности. Например, построение оптимального
Задачи составления расписаний возникают в частности:
• на транспорте при составлении расписания движения поездов, самолетов, общественного городского транспорта;
• при планировании занятий в учебных заведениях;
• при планировании занятости персонала, например, дежурства врачей;
• при выполнении сложных продолжительных проектов строительства зданий, кораблей и т.п.;
• при планировании проведения спортивных мероприятий;
• в компьютерных сетях при планировании очередности передачи пакетов информации и т.д.
Из выше изложенного можно сделать вывод, что подобные задачи актуальны. В дипломной работе рассматривается известная NP - полная в сильном смысле задача теории расписаний для одного прибора: задача минимизации
максимального временного смещения. [1]
В ходе данной работы были изучены постановки и методы решения известной NP-полной задачи теории расписаний - минимизации максимального временного смещения для одного прибора. Был разработан программный проект, включающий приближенные алгоритмы решения этой задачи. Один из алгоритмов представляет собой реализацию общей схемы решения задачи, второй - обобщенное правило Джексона (из всех поступивших требований на текущий момент выбирать с минимальным директивным сроком).
Разработанный программный проект достаточно универсален. Интерфейс удобен для тестирования алгоритмов и для их экспериментального исследования. В проекте предусмотрены различные способы ввода данных и вывода результатов.
Также был проведен численный эксперимент сравнения решений найденных предложенными алгоритмами. Эксперименты проводились с размерностями от 5 до 1000, для определенной размерности было сгенерировано и решено по 100 примеров. Из проведенных экспериментов было выявлено:
при размерности задачи = 5, в 38% примеров значения целевой функции совпали, в 2% примеров F1/F2 < 1, в 26% примеров F1/F2 < 1.1, в оставшихся 34% примеров F1/F2 < 1.7;
при размерности задачи = 10, в 15% примеров значения целевой функции совпали, в 8% примеров F1/F2 < 1.02, в 42% случаях F1/F2 < 1.05, в оставшихся 35% примеров F1/F2 < 1.16;
при размерности задачи = 20, в 13% примеров значения целевой функции совпали, в 22% примеров F1/F2 < 1.01, в 34% примеров F1/F2 < 1.05, в 30% примеров F1/F2 < 1.12;
при размерности задачи = 30, в 8% примеров значения целевой функции совпали, в 17% примеров F1/F2 < 1.01, в 31% примеров F1/F2 < 1.03, в 44% примеров F1/F2 < 1.09;
при размерности задачи = 50, в 7% примеров значения совпали, в 28% примеров F1/F2 < 1.01, в 24% примеров F1/F2 < 1.02, в 41% примеров значение F1/F2 < 1.05;
при размерности задачи = 100, в 4% примеров значения совпали, в 24% примеров F1/F2 < 1.005, в 53% примеров F1/F2 < 1.015, в 19% примеров F1/F2 < 1.02;
при размерности задачи = 500, в 3% примеров значения совпали, в 43% примеров F1/F2 < 1.002, в 28% примеров F1/F2 < 1.003, в 26% примеров F1/F2 < 1.004;
при размерности задачи = 1000, в 1% примеров значения совпали, в 40% примеров F1/F2 < 1.001, в 59% примерах F1/F2 < 1.002.
Из этого можно сделать вывод, что при увеличении размерности задачи процент совпадения решений уменьшается. Было определено, что в 88% примеров расписания с меньшим значением целевой функции были построены вторым приближенным алгоритмом (обобщенное правило Джексона), в 12% примеров значения целевой функции совпадают.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
