ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ

Актуальность данной работы состоит в необходимости разработки нового алгоритма и метода решения трудноразрешимой задачи оптимизации, которая имеет широкое практическое применение. Таким алгоритмом является, в частности, генетический алгоритм, который основан на процессах естественного отбора (мутация, скрещивание, отбор) и является частью более широкого направления искусственного интеллекта – эволюционных вычислений. В настоящее время существует множество задач оптимизации теоретической информатики. Задача оперативно-календарного планирования – это комбинаторная задача оптимизации, главная цель которой – найти расписание с минимальным временем работы для обработки j заданий на множестве m машин. График обработки заданий в задаче оперативно-календарного планирования подвергается некоторым ограничениям, например, только одна операция задания может обрабатываться на одной машине за раз, операции задания должны обрабатываться в определённом порядке, а приостановка любой операции – запрещена. Теория расписаний – это хорошо известная и очень NP-трудная задача, а также доказала, что она является сложно вычисляемой задачей. Анализ проблемы теории расписаний обеспечивает адекватное понимание решения проблем планирования, которые возникают в более сложных и реалистичных системах. Поэтому эвристика предпочтительнее для решения вопросов оперативно-календарного планирования. Генетический алгоритм (ГА) считается наиболее известным методом оптимизации для класса комбинаторных задач. Также, ГА хорошо известны для решения задач оптимизации теоретической информатики. Из вышеуказанного следует, что разработка генетического алгоритма для решения задачи оперативно – календарного планирования сейчас востребована. Основная цель работы – разработка алгоритма поиска наилучшего расписания в задачах календарного планирования, на основе генетического алгоритма. Для реализации поставленной цели предполагается решить следующие задачи: изучить теорию генетических алгоритмов, решающих задачу календарного планирования; разработать программу на основе генетического алгоритма, предназначенную для поиска минимального времени, которое необходимо затратить для решения работы; провести тестирование программы для поиска номера поколения, в которой было найдено наилучшее время для выполнения работы предприятия. Объектом исследования в данной работе является генетический алгоритм решения задачи оперативно – календарного планирования. Предметом исследования является качество работы генетического алгоритма задачи календарного планирования для различных входных расписаний работы предприятия. Информационной базой исследования являются результаты работы программы. Методологическая основа исследования включает в себя эмпирический метод (многократный запуск программы на различных наборах данных о предприятии), сбор статистической информации (нахождение эпохи, в которой было найдено минимальное время для выполнения работы на предприятии при разных значениях коэффициента кроссовера и мутации для выполняемого алгоритма), графический метод (построение графиков зависимостей качества работы генетического алгоритма от размера составляемого расписания (N?M), где M – количество машин на предприятии, N – вычисляется путём сложения количества операций, которые необходимо совершить для каждой конкретной работы), анализ полученных зависимостей. Научная новизна заключается в том, что предлагается новый генетический алгоритм решения задачи календарного планирования предприятия. Теоретическая и практическая значимость работы состоит в широком применении алгоритмов решения задачи календарного планирования. Например, планирование операций считается наиболее важным вопросом управления производственными процессами и планирования. Планирование связано с присвоением рабочих мест производственным ресурсам и указанием последовательности для оптимизации определённых целевых функций. В наше время задачи составления расписаний широко распространены во многих областях производства, где существует возможность большого выбора различных последовательностей выполнения определённых работ. И эта задача заключается конкретно в том, чтобы отыскать оптимальное расписание, а точнее – найти последовательность работ (каждая из которых выполняется за определенное время), выполнение которых приведёт нас в итоге к минимально затраченному ресурсу – времени. ?