Оптимизация производственных расписаний с помощью генетического алгоритма

23 сентября 2018 - Администратор

Наша жизнь становится всё более компьютеризованной. Компьютеры появляются в виде ПК (персональных компьютеров), КПК (Карманный персональный компьютер). Они появляются также и на производстве. На предприятиях они заменяют рабочую силу, делая полученный продукт дешевле, и, делая производство проще и быстрее. Но до сих пор существует проблема распределения задач. Для решения этой проблемы компании тратят много времени, а, следовательно, и денег, на решения данной проблемы.  Конечно, для её решения было создано немало программ, например Pharis (UNIS, Чешская республика, г. Брно) или наша отечественная СПРУТ-ОКП (ЗАО "СПРУТ-Технология" Россия, Набережные Челны).

Рис. 1 Окно существующей программы Pharis.

Но у них всех есть один общий недостаток: дороговизна и (для большинства) невозможность работать в реальном времени (Real-time или RT). Кроме того данные комплексы как правило  опираются на эвристические подходы поиска оптимальных расписаний, а значит могут работать не совсем эффективно и корректно при определенных ситуациях.

Именно поэтому целью нашей работы было создание доступной программы,  способной оперативно формировать  оптимальное производственное расписание. Так как алгоритмизация должна быть наиболее эффективной, то особенно важно оптимизировать их структуру, чтобы снизить время простоев производства, а, следовательно, и цену конечного продукта. Задача в общем виде имеет экспоненциальную размерность, поэтому простым перебором ее решить не возможно. В нашем проекте для преодоления этой сложности используется Генетический алгоритм. Он показал хорошую сходимость для различного количества задач, сравнительно быстро находил оптимальный алгоритм. Оптимизация  оценивалась по суммарному времени выполнения всех задач, искался минимум.

Проблема: Ежегодно увеличиваются расходы предприятий из-за  не оптимального оперативного планирования производственных расписаний. Необходим  дешевый эффективный программный комплекс, создающий  оперативное  оптимальное  производственное расписание.

Цель проекта: Разработка программного комплекса способного сформировать оптимальный производственное расписание с помощью генетического алгоритма.

Объект исследования: Оптимальные производственные расписания. MES – технологии.

Предмет исследования: Алгоритмы оптимизации производственных расписаний,  созданные на основе генетических алгоритмов.

Задачи исследования:

1.      Реализовать генетический алгоритм поиска оптимального выполнения задач.

2.      Протестировать программу.

В ходе выполнения работы использовались следующие методы и приёмы: изучение литературных источников, математическое моделирование, программное моделирование на языке C++ и Java.

Описание алгоритма формирования оптимального производственного расписания.
 Постановка задачи.

Имеется набор задач, для каждой,  из которой определен объем. Имеются несколько процессоров (исполнителей) равной мощности. Необходимо  распределить  задачи по процессорам и интервалам времени, чтобы суммарное выполнение всех задач было минимальным.

Данная задача решается с помощью генетического алгоритма.

Моделирование оптимального алгоритма.

В основе моделирования лежит генетический алгоритм. Суть генетического алгоритма  заключается в следующем: отбирать наиболее подходящие решения и генерировать из них еще более оптимальные варианты на основе алгоритмов отбора, скрещивания и мутации. Так до тех пор, пока не будет найдено решение. Краткий алгоритм генетического алгоритма:

На данном  этапе разработке можно повлиять на следующие параметры: количество интервалов времени, количество «исполнителей» (процессоров) и количество задач.

 Идея алгоритма.

алгоритм

 

Хромосома  алгоритма определялась следующим способом.

 Временной непрерывный  интервал разбивался на промежутки.

Хромосома - это массив,  у которого  для каждого интервала времени  и процессора , определялось значение – номер задачи , которую будет выполнять данный процессор(исполнитель) в заданный интервал времени.

  Уникальность предложенной методики заключалась в расчете Фитнес функция генетического алгоритма.  Фитнес функция определялась  следующим образом:

Определялись все занятые интервалы времени, более поздние имели больший вес, все занятые интервалы суммировались с учетом веса. Таким образом, чем больше занято интервалов, тем больше  фитнес функция. Также учитывалось количество переналадок процессоров, количество переналадок  прибавлялось к фитнес функции. Тем самым  лучшая хромосома должна иметь минимально возможное значение фитнес функции.

Опишем поподробнее алгоритм отбора и скрещивания.

Вначале алгоритма формировалось начальное поколение хромосом.  Чтобы сделать максимально репрезентативную выборку, определялся случайный порядок для задач. На данном этапе нет четкой иерархии задач, все задачи равнозначны и могут выполняться в любой очередности. (задача цепочек задач и иерархии это перспективы данного проекта) На следующем этапе производилась загрузка свободных процессоров по интервалам времени, так чтобы все задачи были выполнены.

После того, как было сформировано начальное поколение, запускает цикл с эпохами. Для каждой эпохи производится расчет фитнес функции по всем хромосомам, формируется колесо рулетки , для отбора  в новое поколение, скрещивание  хромосом по случайному гену. Здесь следует обратить внимание , на то что после скрещивания по случайному гену, хромосомы должны обменяться еще двумя генами со значениями, которые были отданы. Это необходимо чтобы все задачи были выполнены в полном объеме.

Алгоритм  реализовывался на языке программирования Java, это позволило создать дружественный интерфейс.

Алгоритм показал хорошую сходимость  суммарное значение  фитнес функции  падает , т.е. алгоритм ищет оптимальное значение самого быстрого решения всех задач с минимальным количеством переналадок.

Заключение        

Решены сформулированные задачи проекта:

1. Реализован генетический алгоритм поиска оптимального производственного расписания для задач без четкой иерархии.

2. Программа протестирована на различных вводимых данных. Алгоритм показал высокую сходимость для различный конфигураций, более чем на 100 тестах. Программа находила оптимальное решение менее чем за 15000 итераций.

В целом реализованный алгоритм показал хорошую сходимость к оптимальному результату и может быть использован для решения общей задачи оптимизации, в которой учитывалось бы иерархия задач, гибкая настройка мощности процессоров, цены переналадок оборудования и прочее.

 

Перспективы проекта:

1.      Возможность задания иерархии задач (последовательности следования задач).

2.      Увеличение размерности алгоритма (большое количество задач , интервалов времени).

3.      Внедрение программного комплекса в реальное производство.

4.      Совершенствование генетического алгоритма путем ускорения его работы с помощью методов параллельного программирования.

Комментарии (0)

Нет комментариев. Ваш будет первым!