Введение
Определения 5
1. Математическая модель 6
2. Постановка задачи 7
3. Задача двух машин 8
4. Эвристические алгоритмы 10
5. Численный эксперимент 15
Заключение 17
Список литературы 18
Приложение 19
В течение всей жизни и во многих сферах человеческой деятельности мы сталкивается с расписаниями: расписание в школе, транспорта, телевизионных передач. Все мы стараемся разумно на наш взгляд составить его, а для некоторых это становиться профессией. Им приходится разрабатывать календарные планы работы предприятий и учреждений, составлять расписание движения транспорта, организовывать учебный процесс и т.д. Сама по себе временная увязка множества действий, сопряженных с достижением заданной цели, достаточно сложная задача.
Весьма глубокие исследования в этом направлении начались с 50-х годов XX-го века. В это время появился термин “теория расписаний”, предложенный Р. Беллманом в 1956 году. Данное направление в науке, берет свое начало с работы Генри Гантта 1903 г., который предложил то, что сегодня называют, диаграммой Гантта. Сама теория расписаний является одним из разделов исследования операций.
В данной дипломной работе рассматривается одна из задач теории расписаний - составление расписания для взаимозаменяемых машин, где критерием оптимальности служит минимальное значение некоторой функции.
Люди на протяжении всей жизни сталкиваются с необходимостью составления расписания. Мы знаем что и к какому сроку нужно сделать и также представляем какое время нам потребуется на каждое дело. Исходя из этих данных мы составляем расписание. Практически все расписание руководствуется “похожими алгоритмами”, стремясь сделать все и вовремя.
Например, составления личного расписания не вызывает сложности. Но сложности появляются тогда, когда работы становиться много и нужно учесть много факторов и дополнительных условий и не для одного человека, а для большого количества, например, десятка рабочих и сотни работ.
Существуют методы решения данной задачи и один из первых - это точный, но программы на основе таких методов работают очень долго.
Моим научным руководителем было предложено разработать методы, которые решают данную задачу быстрее, чем это делают точные.
Цель дипломной работы:
Создать алгоритм(ы), которые бы составляли достаточно оптимальное расписание для взаимозаменяемых машин за короткое время(значительно быстрее, чем точные алгоритмы).
Задачи:
1. Изучить имеющиеся методы решения задачи.
2. Разработать эвристические алгоритмы составления расписания.
3. Разработать программу, реализующую разработанные алгоритмы.
4. Проанализировать алгоритмы и выяснить, какой из
алгоритмов лучше составляет расписание.
В ходе работы были поставлены следующие задачи:
1. Изучить имеющиеся методы решения задачи.
2. Разработать эвристические алгоритмы составления расписания.
3. Разработать программу, реализующую разработанные алгоритмы.
4. Проанализировать алгоритмы и выяснить, какой из алгоритмов лучше составляет расписание.
В первых частях было написано, что из себя представляет задача.
Далее было реализован один из точных алгоритмов и показано, что такой алгоритм работает очень долго. Даже незначительное увеличение количества машин и операций во много раз увеличивает время выполнения программы.
Были разработаны несколько алгоритмов и проведен численный эксперимент. На основе полученных данных и с использованием разных критериев были даны рекомендации, какими алгоритмами пользоваться для составления расписания.
В данной дипломной работе были разработаны эвристические алгоритмы составления расписания для взаимозаменяемых машин. Было разработано несколько алгоритмов и с помощью численного эксперимента и нескольких критериев были даны рекомендации какими именно алгоритмами пользоваться.
