Оперативно-производственное планирование на предметно-замкнутом участке (стр. 3 из 3)

Количество деталей в партии обработки p обозначим

; тогда должны иметь место равенства

(19.1)

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

Задача формулируется следующим образом: найти число партий обработки P, количество деталей

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

Эволюционные методы решениия NP-трудных задач

Эволюционные методы (ГА), как и ИНС, позволяют решать вспомогательные задачи теории управления, не привлекая такие базовые понятия, как интеграл, дифференциал, передаточная функция динамического звена и т.п.

В эволюционных методах вначале создается множество случайно сформированных объектов с заданной структурой (такое множество называется популяцией объектов) и функция, определяющая близость объекта к истинному решению, называемая функцией цены. Далее все эволюционные методы работают по общей схеме: определяется цена объектов в популяции, с учетом цены и при внесении элемента случайности создаются объекты для популяции следующей итерации. Данный процесс повторяется либо до получения решения, либо до окончания времени, отведенного на решение. Популяция имеет "память" - в ней накапливаются лучшие результаты предыдущих итераций, и этим эволюционные методы отличаются от других методов случайного поиска. В создании нового объекта популяции обычно участвуют два существующих объекта, от каждого из которых новый объект отбирает часть свойств; этот процесс называется скрещиванием или кроссинговером. При кроссинговере, кроме того, исходные объекты подвергаются некоторому случайному изменению - мутации. Иногда используется так называемая стратегия элитизма, при которой несколько лучших особей переходят в след поколение без изменений, не участвуя в кроссинговере и отборе.

Эволюционные методы представляют собой модель биологического процесса эволюции: в популяции идет борьба за существование; с течением времени объекты совершенствуются и выживают сильнейшие.

В литературе направление исследований, объединяющее различные эволюционные методы, получило название "эволюционные вычисления".

Рис.2. Основные операторы генетического алгоритма
(анимация - 8 циклов повторения)

Обычно все алгоритмы эволюционных вычислений состоят из следующих шагов:

1. Задается структура объектов, функция цены и условия останова
2. Создается популяция объектов Р
3. С помощью функции цены из популяции Р выбирается множество лучших объектов
4. С помощью операторов, поддерживающих эволюцию, из выбранных объектов создаются новые - претенденты на включение в следующую популяцию.
5. Образуется новая популяция Р из отобранных на 4-м шаге объектов.

Шаги 3-5 повторяются до выполнения условия останова.

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

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

Широкому распространению эволюционных вычислений способствует три причины.

· Данные алгоритмы для многих типов задач показали свою эффективность по сравнению с другими методами.

· Естественный отбор устраняет необходимость заранее учитывать все особенности решения задачи. Можно успешно решать задачи, структуру решения которых программист не знает. Существует много примеров решения с помощью эволюционных вычислений многих практических задач (задача коммивояжера, задачи распределения ресурсов; решение задач в реальном времени, связанных с управлением движущимися объектами).

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

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

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

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

Заключение

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

Список использованной литературы

1. Усков А.А. Интеллектуальные технологии управления, М:Горячая линия – Телеком, 2004.
2. Егоров М.Е. Основы проектирования машиностроительных заводов, Высшая школа, 1969.
3. Егоров М.Е. Технология машиностроения, Высшая школа, 1976.
4. Мосталыгин Г.П. Технология машиностроения, Машиностроение, 1990.
5. Суслов А.Г. Научные основы технологии машиностроения, Машиностроение, 2002.
6. Каменицер С.Е. Автоматизированная система управления машиностроительным предприятием, Машиностроение, 1971.
7. Глушков В.М. Планирование дискретного производства в условиях АСУ”, Техника, 1975.
8. Соколицын С.А. Многоуровневая система оперативного управления ГПС в машиностроении, Политехника, 1991.
9. Смоляр Л.И. Модели оперативного планирования в дискретном производстве, Наука, 1978.
10. Шкурба В.В., и др. Планирование дискретного производства в условиях АСУ. Техніка, 1975.