автореферат диссертации по машиностроению и машиноведению, 05.02.22, диссертация на тему:Разработка модели, методов и программного обеспечения для оперативного планирования производства на основе теории адаптации и технологии программных агентов

005007671

На правах рукописи УДК 658.012.2

ГРОМОВ СЕРГЕЙ АЛЕКСЕЕВИЧ

РАЗРАБОТКА МОДЕЛЕЙ, МЕТОДОВ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ ОПЕРАТИВНОГО ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА НА ОСНОВЕ ТЕОРИИ АДАПТАЦИИ И ТЕХНОЛОГИИ ПРОГРАММНЫХ АГЕНТОВ

Специальности: 05.02.22 - Организация производства (машиностроение)

05.13.17 - Теоретические основы информатики

птгт

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2011

005007671

Работа выполнена в Московском государственном техническом университете им.Н.Э.Баумана

Научный руководитель:

Научный консультант:

Официальные оппоненты:

кандидат технических наук, доцент Тарасов Валерий Борисович

кандидат технических наук, доцент Афонин Павел Владимирович

доктор технических наук, профессор Захаров Михаил Николаевич

кандидат технических наук, доцент Гладков Леонид Анатольевич

Ведущая организация: Российский научно-исследовательский

институт информационных технологий и систем автоматизированного проектирования

Защита состоится « /Э » Яи^т^ 2012г. в _часов на

заседании диссертационного совета Д.212.141.05 Московского государственного технического университета им.Н.Э.Баумана по адресу: 105005, Москва, 2-я Бауманская ул., д.5.

Ваш отзыв на автореферат в одном экземпляре, заверенный печатью просим выслать по указанному адресу.

С диссертацией можно ознакомиться в библиотеке Московского государственного технического университета им. Н.Э. Баумана

Телефон для справок (499)2670963

Автореферат разослан « <ь » 2011 г.

Ученый секретарь

диссертационного совета Д.212.141.05

к.т.н., доцент к^Рг Силаева Л.А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность. Планирование является неотъемлемой частью организации современного машиностроительного производства. Здесь наблюдаются две противоположные тенденции: с одной стороны для массового производства характерна некоторая предопределенность, выраженная узкой специализацией и крупными партиями выпускаемых изделий, а с другой стороны, в условиях труднопредсказуемого рынка и изменчивости спроса, наблюдается индивидуализация требований заказчиков и снижение объемов заказываемых партий. Наиболее остро это противоречие выражается на уровне оперативного планирования производства, которое должно обеспечивать эффективное управление в динамичных условиях. Таким образом, сотрудникам планово-диспетчерских служб, осуществляющим разработку оперативных планов, становится все труднее исполнять свои обязанности. Средством решения этих проблем является использование информационных систем. Среди них наибольшую популярность приобрели системы MRP/ERP, охватывающие существенный объем задач планирования и управления ресурсами производственного предприятия. Кроме того используются специализированные приложения, такие как производственные исполнительные системы MES (Manufacturing Execution System) и системы оптимизированного (синхронного) планирования APS (Advanced Planning & Scheduling). Сегодня широко освещены примеры успешного внедрения этих систем на площадках массовых производств различных отраслей. Однако опыт показывает, что далеко не всегда можно применить существующее на рынке тиражное решение в реальной жизни. Прежде всего, проблемы, связанные с внедрением того или иного программного приложения, обусловлены производственной спецификой отрасли, а подчас и особенностями конкретного предприятия. Игнорирование этих особенностей или же заведомое упрощение модели процесса приводит к формированию плана, невыполнимого в реальных производственных условиях, что в свою очередь сводит на нет результаты, полученные при помощи средств автоматизации. В целом, уровень оперативного планирования играет ключевую роль в организации производства, непосредственно определяя сценарий работы производящих цехов.

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

Объектом исследования являются сложные производственные системы оперативного планирования, рассматриваемые в плане сокращения времени подготовки плана и повышения его качества.

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

Целью работы является повышение эффективности оперативного планирования производства за счет разработки моделей, алгоритмов и программных средств автоматизированного планирования.

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

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

2. Анализ типовых формулировок задач оперативного планирования производства.

3. Математическая постановка задачи построения и оптимизации производственного расписания. Обзор методов ее решения.

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

5. Разработка гибридного алгоритма эвристического поиска в пространстве состояний на основе предложенной многоагентной модели и модифицированного генетического алгоритма.

6. Программная реализация разработанных алгоритмов.

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

Методы исследования. При выполнении диссертации использованы методы системного анализа и исследования операций, математического программирования и теории расписаний, теории алгоритмов и теории графов, теории программных агентов и многоагентных систем, теории адаптации и коллективного поведения, эволюционного моделирования и генетического поиска, аппарат теории вероятностей и нечетких множеств.

Среди работ в области исследования операций, планирования производства и теории расписаний следует отметить основополагающие труды таких ученых как: Х.Ахьюджа, Г.Вагнер, Д.Джонсон, М.Гэри, Дж.Р.Джексон, М.Н.Захаров, Р..Конвей, АКофман, ААКолобов, БАЛагоша, ААЛазарев,

B.Г.Митрофанов, И.Н.Омельченко, М.Л.Пинедо, Г.С.Поспелов, Д.А.Поспелов, Л.И.Смоляр, В.Л.Сосонкин, В.С.Танаев, Е.Б.Фролов, Е.КХоботов, В.В.Шкурба,

C.Элмаграби. При разработке методов и алгоритмов планирования на основе подходов искусственного интеллекта автор опирался на публикации ведущих отечественных и зарубежных специалистов по эволюционному моделированию и генетическим алгоритмам (Дж.Холланд, Л.Дэйвис, Д.Голдберг, Д.Фогель, Д.И.Батищев, И.Л.Букатова, В.В.Емельянов, В.М.Курейчик, Б.К.Лебедев, И.П.Норенков), труды родоначальников теории искусственных агентов, коллективного поведения и многоагентных систем (К.Хьюитт, М.Л.Цетлин) и работы других известных ученых в этой области (М.Вулдридж, В.И.Городецкий, И.Демазо, Н.Дженнингс, К.Лэнггон, К.Маэс, Ж.Фербе, В.Г.Редько, Р.Саттон, П.О.Скобелев, Л.А.Станкевич, В.Б.Тарасов, В.Ф.Хорошевский).

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

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

Результаты работы получены в ходе выполнения проектов РФФИ №03-0790012, 07-07-00418, 08-07-00337, 08-07-00337, 11-07-00780, 11-07-13165-офи-м-2011-РЖД.

Практическая ценность. Предложенные методы и модели реализованы в виде программ на ЭВМ на языке программирования ANSI С++ с использованием библиотеки STL. Разработанные методы позволяют формировать оперативный план производства с учетом цеховых ограничений. Созданный программный инструментарий позволяет существенно сократить время составления плана, а также обеспечивает возможность его быстрой корректировки. Реализованный программный комплекс интегрирован с ERP-системой ORACLE e-Business Suite, с информационной системой 1С 7.7 и использован при автоматизации бизнес-процессов оперативного планирования производства. Архитектура предложенного решения поддерживает большинство промышленных платформ: UNIX, Linux, WIN NT, а также позволяет осуществлять интеграцию с прочими информационными системами.

Внедрение и реализация результатов. Результаты исследований, проведенных в диссертационной работе, были внедрены на отечественных предприятиях ОАО «Лебедянский», ЗАО НПО «Тяжпромарматура» и ЗАО «ФМРус», а также использованы в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана.

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

Апробация работы. Основные результаты работы докладывались на: Международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2002г.), Научной сессии МИФИ-2002 (Москва, 2002г.), Il-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2003г.), Международных научно-технических конференциях IEEE AIS'03 и CAD-2003 (Дивноморское, 2003г.), Международных научно-технических конференциях IEEE AIS'04 и CAD-2004 (Дивноморское, 2004г.), Ш-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте». (Коломна, 2005г.), практическом семинаре «Решения ORACLE для пищевой промышленности» (Москва, 2007г.), IV—й Международной научно-практической конференции

«Интегрированные модели и мягкие вычисления в искусственном интеллекте». (Коломна, 2007г.), Vl-й Международной научно-практической конференции «Интегрированные модели и мягкие вычисления в искусственном интеллекте». (Коломна, 2011г.), а также на Всероссийской конференции «Эффективные методы автоматизации технологической подготовки и планирования производства» (Москва, 2011г.)

Публикации. По теме диссертации автором опубликовано 15 работ, из них 3 - в изданиях, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 161 наименование, и 2 приложений. Объем основного текста работы составляет 155 страниц, включая 34 рисунка и 14 таблиц. Полный объем диссертации составляет 181 страницу.

На защиту выносятся:

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

2. Схема каскадного разрешения ресурсных конфликтов и нарушения ограничений в ходе адаптивного построения производственного расписания.

3. Модифицированные генетические операторы кроссинговера и мутации, снабженные экспертными правилами, которые обеспечивают удовлетворение организационно-технологических ограничений.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

предприятий. Существуют различные классы информационных систем, реализующие современные методологии планирования производства в машиностроении. Наиболее известными являются MRP- и ERP-системы первого и второго поколений, а также недавно разработанные MES и APS-системы. На рис.1 представлен цикл планирования, используемый многими промышленными предприятиями. Здесь показано, какие функции цикла охватывают рассматриваемые классы_информаных^истем.________

rËRP

MES

Исполнение опер.плана производства в цехах

иценка исполнения опер.плана производства

НЗП, текущие запасы

—[ Спецификации

Диспетчеризация производства (DPU)

I ех.карты, операции, произв ресурсы

Оперативное планирование (ODS)

Сменно-суточные задания на рабочие места цеха

Расписания загрузки произв. оборудования

Бизнес-планирование

i

Прогноз продаж -> План продаж

Календарный план производства (MPS)

План потребности в материалах (MRP)

План потребности в мощностях (CRP)

Уточненный календарный план производства

Управление цепочками поставок (SCM)

! APS

Сеть поставщиков сырья и материалов, смежники, и.т.д.

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

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

Традиционно проблема составления оперативного плана на машиностроительных производствах решалась силами предметных

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

Во второй главе дана формализация процесса оперативного планирования на примере поточного производства, проведено исследование сложности поставленной задачи и обзор методов ее решения.

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

Для обоснования предлагаемого подхода к организации процесса составления расписаний ниже приведена формулировка прикладной задачи построения производственного расписания для поточных линий массового производства.

Дано:

1. Множество машин - производственных линий М, \М\=т, каждая линия характеризуется определенным перечнем параметров, значения которых накладывают дополнительные ограничения при определении работ. График недоступности производственных линий задает сервисные интервалы или ремонты [sfy, sey/], их границы обозначают соответственно начало и окончание 1-го сервиса на j-й линии. Также известно RQ - общее количество технологической оснастки.

2. Конечное множество заданий Л/, \N\=n, каждое задание состоит из одной операции. Задание есть элементарная работа, подлежащая выполнению, оно характеризуется: номером машины т„ 1<m,<m; длительностью f, , выраженной в часах; индивидуальным директивным сроком dj, выраженным в часах; признаком необходимости использовать оснастку rq, е{0,1}.

Матрица инцидентности R определяет соотношение между заданиями и производственными линиями. Значение элемента матрицы r¡¡ отражает приоритет выбора j-й линии для выполнения i-го задания, если i-e задание не производится на j-й линии.

Здесь И/Г-матрица переналадки линии задает вспомогательное время, требуемое на переход с выпуска i-го задания на j-e, причем Щ> 0.

Определить:

Разбиение N=N1^jN¿-J..yjNm множества заданий N на т непересекающихся подмножеств, такое что:

1) распределение заданий по линиям соответствует матрице инцидентности R, т.е. vmsM V¿eN имеем г. «оо;

' т Ш

2) для заданий осуществляется выбор предпочтительных линий, что соответствует критерию —>min;

¡sn""

3) для каждого подмножества Nm на горизонте планирования D существует расписание (упорядочение) om'-Nm-*{0,1,...D}, которое удовлетворяет условиям:

a. последовательности выполнения заданий на одной линии, с учетом требования переналадок, не повторяются,

b. Уп , eN \и.=>сг (п. ,)>ег (n)+t.+wt.r^.гДе оь-Функция

1+1 т i mv i+V лЛ i /(¡+1)

очередности;

c. не нарушается график сервисных интервалов т-й линии, т.е.

V n¡ eNm имеем условия [^("/М^т/^тЛ ;

1 <rM+tielsbml>sem¡]

d. одновременно загружено допустимое количество линий

V т е{0,1.....D}, 3 N'CZN: Te[am{n¡)\ ат{п)Щ, |A/r| < rnmax , где

Мтах ^ П)\

e. также соблюдается ограничение единовременного использования оснастки, V г e{0,1,...,D}, NTRQClNT: Vn, g Ntrq Щп1~ 1, I NrRQ\ < RQ.

4) Для всего расписания обеспечивается минимизация целевой функции (ЦФ) F-*min, где F отражает количество заданий, для которых не выполнены индивидуальные директивные сроки,

F = z|<7 (nj+tj-dj j->min • i

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

Объект адаптации (оперативный р план)

и

Блок адаптации

Подсистема^адапта

Блок оценок

дии

В третьей главе

диссертации в качестве новых компьютерных

методов для решения задач ТР предложено

использовать комбинацию методов эволюционного моделирования на основе генетических алгоритмов, а также методов адаптации программных агентов. Процесс планирования

Рис.2, планирование « систем ;

адаптации 0бщая схема данного

подхода приведена на рис.2. Применительно к задаче оперативного планирования имеем: X - состояние среды, которое задается исходными данными для процесса оперативного планирования: потребность в выпуске изделий, с указанием директивных требований, производственные ресурсы, и.т.д.; у- состояние объекта, определяемое вариантом оперативного плана. Помимо среды на состояния объекта влияет управляющее воздействие ц

используемое в преобразовании Я, которое изменяет состояние объекта: У=Г(Х,У).

Команды управления и генерируются блоком адаптации с тем, чтобы подать управляющее воздействие на объект управления, т.е. скорректировать план. Для функционирования блока оценок ему надо задать цель г*, к которой следует стремиться в процессе управления. Для блока адаптации необходимо передать алгоритм управления ср - указание, как добиться поставленной цели. Таким образом, управление задается как: и = <р(Х). Как видно, управление связано, прежде всего, с целями г', которые формирует пользователь системы планирования. Цель адаптации формулируется в виде вектора 2' =(г'1,...,г'1[), который задает критерии и ограничения оперативного планирования, представленные ранее в постановке задачи планирования.

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

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

Блок адаптации

Агент

Обфгтадаптации - Оперативн&^/план

Время | ^ | 0) 1| 21 3| 4| 5| $М\ 8| 9|10|11|12

Линия 1 ' -

Пиния 2 __ ____

-----

Линия 3 1% \

_Агент

-Агент

Агент

Рис.3. Составление расписания коллективом агентов

единственного, подотчетного ей производственного задания из оперативного плана.

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

ограничений. Для всего коллектива агентов глобальная цель адаптации заключается в оптимизации значения целевой функции. Таким образом, в процессе поиска решения каждому агенту необходимо подобрать значения его вектора атрибутов ук, которые оптимизируют значение целевой функции; при этом будут наилучшем образом выдержаны директивные требования и не будут нарушаться поставленные ограничения. Поисковая процедура вариации значений атрибутов задания ук = (Укь Ук2Укп) сводится к выполнению определенных операторов. В нашем случае под операторами, которые осуществляют направленный переход от одного решения к другому, подразумеваются эвристические правила или действия. Применимость того или иного правила зависит от так называемой ситуации или предпосылок, инициирующих выбор наиболее актуального действия. С этой целью предварительно формализуются конечные наборы характерных для отрасли, предприятия или конкретной задачи действий А и ситуаций 5, которыми руководствуются плановики в процессе составления планов. Предполагается, что ситуация должна отражать текущее состояние агента, а именно, должно быть показано, нарушает ли агент какое-нибудь ограничение или насколько он близок к достижению локальной цели, т.е. выполнены ли директивные требования. Именно для организации процедуры направленного перехода от одного решения к другому каждый агент наделяется возможностью выполнять действия, изменяющие его состояние. Для этого в качестве архитектуры агента принята схема анимата на основе обучения с подкреплением, принцип которого проиллюстрирован на рис.4.

Непосредственно процедура поиска в адаптивной системе имеет итерационный характер. За одну итерацию каждый агент должен: 1) в соответствии с вектором состояния

Ук = {УкЬ Ук...... Укп)

актуальную ситуацию где дискретное модельное время адаптивной системы: ¡=1,2.....;

-► Агент

Г,

Среда

-и-

а,

Sr-^l

определить

I _ Рис.4. Обучение с подкреплением

в модели анимата

2) согласно актуальной ситуации по матрице обучения <2 произвести выбор наиболее адекватного действия а,, а, = аг£шах0(2'(#>а));

3) реализовать выбранное действие, применив соответствующий оператор, корректирующий значения вектора атрибутов у= а, (у[);

4) оценить целесообразность предпринятого действия, получив сигнал подкрепления от среды г,, и рассчитать значение Д£>'от сигнала подкрепления г,\

5) скорректировать значение соответствующего элемента ^матрицы обучения О в соответствии с полученной оценкой

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

1-й агент, «л

Послед-ль

|—»(пос

Инициатс

/

Послед-ль]Инициатор

Г Главный Л у инициатор )

1-й уровень каскада

Инициатор]

Послед-ль

->( Последователь ) |

5Г*

►^Последователь ^

I

Инициатор)

.-►/Послед-ль Инициатор)^—'" " 1р)-* 4-Н--\

Последователь

2-й уровень

3-Й уровень

^Последователь ^

Последователь )

Последователь )

Последователь ^ к-й уровень

Рис. 5. Каскадная схема взаимодействия агентов

Вторым подходом в построению блока адаптации, применяемым в диссертации, являются методы эволюционной адаптации, в частности генетические алгоритмы (ГА). На рис.6 представлена схема кодирования хромосомы. Пусть имеется N групп генов, каждая из которых полностью определяет соответствующее задание: первой группе соответствует первое задание, второй - второе, и т.д. Значение гена определяет значение соответствующего атрибута задания.

....Ш...П

Рис.6. Схема кодирования хромосомы

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

В большинстве случаев специфика решаемой задачи закладывается в штрафные функции, используемые при расчете целевой функции агента (особи). Помимо использования штрафных функций предлагается видоизменить логику базовых операторов генетического поиска. Идея модификации сводится к применению правил, которыми руководствуются предметные эксперты в процессе построения расписания. Суть этих правил заключается в направленной корректировке отдельных параметров производственных заданий с целью разрешения коллизий, которые возникают при нарушении ограничений, обусловленных спецификой задачи. Модификация предполагает изменения базовых операторов мутации и кроссинговера. В частности для оператора кроссинговера применяется правило выбора аллелей при реализации скрещивания хромосом. Для наглядной иллюстрации модифицированной логики кроссинговера представлен упрощенный пример, в котором рассматриваются 5 работ и 3 альтернативные производственные линии. Выбраны две хромосомы, представляющие собой различные решения, а именно варианты назначения и последовательность исполнения работ производственными линиями. Каждый прямоугольник помечен индексом соответствующей работы. Прямоугольники расположены по горизонтали вдоль линий, определяющих ту или иную производственную линию. Таким образом, получаем вариацию диаграммы Гантта, чаще всего используемой для визуализации расписаний (рис.7).

Родитель'

D

Линия 1

LJ

Линия 2

5 1 I i

Родитель 2

6 ■ 1 ■ 2

ЛИНИЯ 1

ЛИНИЯ I

Рис. 7. Два варианта расписаний, построенных с помощью генетического алгоритма: родительские пары в модифицированном операторе кроссинговера

3 6 -> 6 3

4 1 -> 4 1

NULL 2 -> NULL 2

1 4 1 4

NULL 5 -> 5 NULL

5 3 -> 3 5

2 NULL •> 2 NULL

6 NULL -> NULL 6

Рис.8. Решение задачи перераспределения работ: логика модифицированного оператора кроссинговера

Потомок 2

Потомок 1

Линия 1

Линия 1

Линия 2

Линия /

Линия 3

Линия '6

Для каждой производственной линии образуем пары работ, по одной из каждого агента. Для каждой пары случайным образом определяем будущую принадлежность потомку. При этом выполняется проверка на дублирование работ в одном и том же решении (рис.8). На рис.9 представлен результат перераспределения работ в результате скрещивания. Получены новые решения, заведомо исключающие нарушения ряда ограничений.

Таким образом, в логику базового генетического

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

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

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

Рис.9. Результат перераспределения работ при использовании модифицированного кроссинговера

Рис. 10. Блок-схема гибридного алгоритма планирования

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

Предложенные алгоритмы планирования были программно реализованы на языке ANSI C/C++ с использованием библиотеки шаблонов STL. Исполнимые модули поддерживают промышленные платформы UNIX, Linux, Win NT.

Экспериментальные исследования, проведенные в диссертации, преследовали две цели: анализ сходимости предложенных алгоритмов, и сравнение их эффективности.

Для анализа сходимости алгоритмов предложено установить характер зависимости временных затрат на поиск решения от размерности задачи (количества работ А/, количества линий М, количество оснастки RD, горизонт планирования D). Под сходимостью понимается достижение такого значения целевой функции F, при котором за последующие ö циклов работы алгоритма изменение AF составит не более А% от предыдущего значения. Для оценки сходимости были взяты следующие величины: 5=10, й%=\%. Исследование проводилось по двенадцати наборам исходных данных, выбранным экспертным путем. На рис.11 представлены полученные зависимости для алгоритма адаптивного поиска и модифицированного генетического алгоритма.

Сходимость алгоритмов

Рис. 11. Оценка сходимости алгоритмов планирования

Кривые роста времени счета с увеличением размерности задачи не сильно отличаются от линейной зависимости. Можно предположить полиномиальную временную

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

Оценка эффективности этих алгоритмов проведена посредством анализа направленности поиска решения. Под направленностью понимается улучшение качества решения. Улучшение оценивается относительно значения целевой функции начального решения. В целях наглядности в эксперимент был включен алгоритм случайного поиска решения. В связи с тем, что в эксперименте рассматриваются различные по структуре алгоритмы, в диссертации были определены единые принципы их сравнения. Г рафики, показанные на рис.12, иллюстрируют полученные результаты. Следует отметить, что все алгоритмы, за исключением случайного, показывает явную направленность поиска.

Эффективность алгоритмов, относительная оценка

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

Далее в работе приводится описание конкретного бизнес-процесса оперативного производственного планирования, который был автоматизирован в рамках внедрения ERP-системы ORACLE. Показан бизнес-шаг «Расчет производственного расписания», логика которого использует предложенные в работе подходы.

В Приложении 1 приведена информация о промышленных объектах, на которых были внедрены результаты диссертации. Приложение 2 содержит вид специально разработанных экранных форм системы ORACLE e-Business Suite для специалистов отдела планирования производства.

—Случайный поиск -о-МП —■—МГА

—н F—у—У—? У1 Г- т—*

300 400 500 600 700 800 900 Количество циклов алгоритма, шт.

Рис.12. Относительная эффективность алгоритмов планирования

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Решена задача планирования загрузки поточных линий в условиях цеховых ограничений. Разработаны алгоритм многоагентного планирования и модифицированный генетический алгоритм, позволяющие учитывать организационно-технологическую специфику при создании оперативного плана производства. Построенные модели каскадного взаимодействия агентов и модифицированные генетические операторы, позволили значительно (в среднем на 20%) сократить фактическое время, требуемое для получения приемлемого варианта плана, удовлетворяющего ограничениям.

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

4. Разработана программная архитектура системы оперативного планирования, опирающаяся на подходы технологии «тонкого» клиента при работе в гетерогенных программных средах. Архитектура предложенного решения поддерживает большинство промышленных платформ: UNIX, Linux, WIN NT, а также позволяет осуществлять интеграцию с прочими корпоративными информационными системами.

5. Внедрение разработанных методов, алгоритмов и программных средств на промышленных площадках ОАО «Лебедянский» и ЗАО «ФМРус» позволило снизить фактическое время, затрачиваемое плановиком на подготовку оперативного плана, от нескольких часов до получаса. Впервые удалось уйти от так называемых «интуитивных» оценок качества плана и применить количественную оценку.

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

Основные результаты диссертации отражены в следующих работах:

1. Громов С.А. Методы адаптивного и генетического поиска в оперативном планировании производства// Известия высших учебных заведений. Машиностроение. - 2011.- №8. - С.74-80.

2. Громов С.А., Тарасов В.Б. Методы искусственного интеллекта в автоматизации оперативного планирования// Программные продукты и системы. - 2007. - №4. - С.89-92.

3. Громов С.А., Тарасов В.Б. Интегрированные интеллектуальные системы оперативного планирования производства// Известия Южного федерального университета. Технические науки. - 2011. - №7. - С.60-67.

4. Громов С.А. Решение задачи загрузки оборудования с помощью алгоритма коллективной адаптации// Интеллектуальные системы и технологии: Научная сессия МИФИ-2002: Сборник научных трудов; В 14-и томах. - М., 2002. Т.З. -С. 196-198.

5. Громов С.А. Применение алгоритма коллективной адаптации в задаче загрузки оборудования// Восьмая Международная научно-техническая конференция студентов и аспирантов: Радиоэлектроника, Электротехника и Энергетика: Тезисы докладов; В 3-х томах. - М., 2002. Т.1.- С.262-263.

6. Громов С.А. Возможности использования ERP-системы для поддержки оперативного планирования производства// Chief Information Officer -руководитель информационной службы. - М., 2006. - № 9 (52). - С.44-49.

7. Громов С.А. Интеллектуализация систем оперативного планирования производства// Сборник трудов Vl-й Международной научно-практической конференции г.Коломна, 16-19 мая 2011 г. - М„ 2011. - Т.2. - С.588-598.

8. Громов С.А., Дубовенко А.А.. Построение модели функционирования многопродуктовой системы управления товарными запасами II Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов ll-го Международного научно-практического семинара. - М., 2003. - С.256-262.

9. Громов С.А., Дубовенко А.А. Применение алгоритмов адаптивного и генетического поиска для минимизации затрат при управлении товарными запасами в многопродуктовой системе// Труды Международных технических конференций IEEE AIS' 03 и CAD-2003, г.Дивноморск, 3-10 сентября 2003,-М., 2003.-Т. 1.-С.34-38.

Ю.Громов С.А., Дубовенко А.А.. Построение модели функционирования многопродуктовой системы управления запасами// Проблемы создания информационных систем поддержки принятия управленческих решений для муниципальных образований. Материалы Московской областной межмуниципальной конференции. - М., 2003. - С.145-148.

11. Громов С.А., Дубовенко А.А. Исследование алгоритмов адаптивного и генетического поиска в задаче управления товарными запасами в многопродуктовой системе// Труды Международных технических конференций IEEE AIS' 04 и CAD-2004, г.Дивноморск, 3-10 сентября 2004г. -М., 2004.-Т.1.-С.34-38.

12. Громов С.А., Дубовенко А.А.. Возможности алгоритмов адаптивного и генетического поиска для решения задач оперативного планирования II Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов Ill-ro Международного научно-практического семинара. - М„ 2005. - С.254-259.

13. Громов С.А., Дубовенко А.А.. Использование экспертных оценок для обучения алгоритмов генетического и адаптивного поиска в задачах оперативного планирования// Интегрированные модели и мягкие вычисления в искусственном интеллекте: Сборник трудов IV—й Международной научно-практической конференции г.Коломна, 28-30 мая 2007г.; В 2-х томах. - М., 2007. Т.1.-С. 308-313.

14. Громов С.А., Тарасов В.Б. Развитие информационных систем поддержки планирования производства: на пути к ERPIII// Реинжиниринг бизнес-процессов на основе современных информационных технологий. Системы управления знаниями: Сборник научных трудов Xlll-й научно-практической конференции, г.Москва, 14 мая 2010 г. - М., 2010. - С.105-112.

15. Афонин П.В., Громов С.А. Разработка генетического алгоритма для решения задачи оперативного планирования производственных заданий// Труды Международного Конгресса по интеллектуальным системам и информационным технологиям: AIS-IT'2010, г. Дивноморск, 2-9 сентября 2010 г. -М„ 2010-Т.З.-С.18-23.

Подписано к печати 14.12.11. Заказ №868 Объем 1,0 печ.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

Принятые сокращения.

Введение.'.

Глава 1. Анализ технологий, методов и средств автоматизации бизнес процессов планирования для промышленных предприятий.

1.1. Место задач планирования в деятельности предприятия.

1.2. Иерархия задач планирования на производственном предприятии.

1.3. Различные подходы к планированию: методологии

MRPII, SCM, JIT.

1.3.1. Стандарт MRP II.

1.3.2. . Планирование цепочек поставок.

1.4. Программные средства и инструменты производственного планирования.

1.4.1. Системы класса ERP и MRPII.

1.4.2. Системы усовершенствованного планирования производства APS

1.4.3. Производственные исполнительные системы-MES.

1.5. Некоторые тенденции развития систем. производственного планирования на предприятиях.

1.6. Проблемы внедрения и промышленного. использования информационных систем планирования. на предприятиях.

1.7. Формулировка цели и задач диссертационной работы.

1.8. Выводы к главе 1.

Глава 2. Формализация задачи оперативного планирования.

Анализ методов решения.

2.1. Теория расписаний — основа оперативного планирования.

2.2. . Объекты и элементы задач теории расписаний.

2.3. Классификация задач построения расписаний.

2.4. Классические задачи теории расписаний.

2.5. Формулировка задачи составления производственного расписания в поточном машиностроении.

2.6. Подходы к решению задач теории расписаний.

2.7. Выводы к главе 2.

Глава 3. Разработка метода оперативного планирования на основе технологии программных агентов и теории адаптивного поведения.

3.1. Оперативное планирование как адаптивная система.

3.2. Классификация видов адаптации.

3.3. Компоненты адаптивной системы агентов.993.4. Разработка модифицированного генетического алгоритма. для построения производственного расписания.

3.4.1. Схема кодирования решения.

3.4.2. Генетические операторы.

3.4.3. Расчет целевой функции.

3.4.4. Условия останова алгоритма.

3.5. Интеграция алгоритмов генетического и адаптивного поиска.

3.6. Выводы к главе 3.

Глава 4. Архитектура и исследование гибридной модели оперативного планирования.

4.1. Программная реализация предложенных алгоритмов.

4.2. Исследования алгоритмов адаптивного и генетического поиска.

4.2.1. Оценка сходимости алгоритмов.

4.2.2. Исследование направленности поиска алгоритмов.

4.3. Бизнес-процесс оперативного планирования производства.

4.3.1. Шаг: Контроль незавершенного производства.

4.3.2. Шаг: Расчет потребности в выпуске продукции.

4.3.3. Шаг: Корректировки потребности в выпуске продукции.

4.3.4. Шаг: Расчет производственного расписания.

4.3.5. Шаг: Оценка качества расписания.

4.4. Техническая и функциональная архитектуры предложенного. решения.

4.5. Выводы к главе 4.

Применение эффективных методологий управления активами предприятия дает существенную выгоду без привлечения дополнительных инвестиций. Практически все имеющиеся методологий уже заложены в функциональность современных информационных систем (ИС). Среди таких ИС наибольшую популярность имеют платформы ERP-класса, охватывающие существенный объем задач планирования и управления ресурсами. Исключение составляют уровни оперативного планирования производства и некоторые задачи управления цепями поставок (SCM), автоматизация которых, как правило, осуществляется с помощью специализированных приложений - систем класса MES (Manufacturing Execution System) и APS (Advanced Planning & Scheduling). Сегодня широко освещены примеры успешного внедрения этих продуктов на производственных площадках предприятий различных отраслей. Однако опыт показывает, что далеко не всегда можно применить существующий на рынке тиражный продукт в реальной жизни. Прежде всего, проблемы, связанные с внедрением того или иного решения, обусловлены спецификой производственной отрасли, а зачастую и особенностями конкретного предприятия. Игнорирование этих особенностей или же заведомое упрощение модели процесса приводит к получению невыполнимого плана в реальных производственных условиях, что в свою очередь сводит на нет результаты, полученные при помощи средств автоматизации. В целом, уровень оперативного планирования играет ключевую роль в организации производства, непосредственно определяя сценарий работы производящих цехов и обеспечивая формирование исполнимых производственных планов, адекватных задачам предприятия.

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

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

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

Целью работы является, повышение эффективности оперативного планирования производства за счет разработки моделей, алгоритмов и программных средств автоматизированного планирования.

Для достижения поставленной цели в диссертации решаются следующие основные задачи:

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

2. Анализ типовых постановок задач оперативного планирования производства.

3. Математическая постановка задачи построения и оптимизации производственного расписания. Обзор методов ее решения.

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

5. Разработка гибридного алгоритма эвристического поиска в пространстве состояний на основе предложенной многоагентной модели и модифицированного генетического алгоритма.

6. Программная реализация разработанных алгоритмов.

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

Методы исследования. При выполнении диссертации использованы методы исследования операций и математического программирования, дискретной оптимизации и теории расписаний, теории алгоритмов и теории графов, теории программных агентов и многоагентных систем, теории адаптации и коллективного поведения, эволюционного моделирования и генетического поиска, аппарат теории вероятностей и нечетких множеств.

Среди работ в области исследования операций, планирования производства и теории расписаний следует отметить основополагающие труды таких ученых как: Х.Ахьюджа, Г.Вагнер, Д.Джонсон, М.Гэри, Дж.Р. Джексон, М.Н.Захаров, Р.Конвей, А.Кофман, А.А.Колобов, Б.А.Лагоша, А.А.Лазарев, В.Г.Митрофанов, И.Н.Омельченко, М.Л.Пинедо, Г.С.Поспелов, Д.А.Поспелов, Л.И.Смоляр, В.Л.Сосонкин, В.С.Танаев, Е.Б.Фролов, Е.Н.Хоботов, В.В.Шкурба, С.Элмаграби. При разработке методов и алгоритмов планирования на основе подходов искусственного интеллекта автор опирался на публикации ведущих отечественных и зарубежных специалистов по эволюционному моделированию и генетическим алгоритмам (Дж.Холланд, Л.Дэйвис, Д.Голдберг, Д.Фогель, 1

Д.И.Батищев, И.Л.Букатова, В.В.Емельянов, В.М.Курейчик, Б.К.Лебедев, И.П.Норенков), труды родоначальников теории искусственных агентов, коллективного поведения и многоагентных систем (К.Хьюитт, М.Л.Цетлин) и работы других известных ученых в этой области (М.Вулдридж, В.И.Городецкий, И.Демазо, Н.Дженнингс, К.Лэнгтон, К.Маэс, Ж.Фербе, В.Г.Редько, Р.Саггон, П.О.Скобелев, Л.А.Станкевич, В.Б.Тарасов, В.Ф.Хорошевский).

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

Результаты работы получены в ходе выполнения проектов РФФИ №0307-90012, 07-07-00418, 08-07-00337, 08-07-00337, 11-07-00780, 11-07-13165-офи-м-2011-РЖД. Практическая ценность. Предложенные методы и алгоритмы реализованы в виде программ на ЭВМ на языке программирования ANSI С++, с использованием библиотеки STL. Разработанное программное обеспечение интегрировано с ERP-системой ORACLE e-Business Suite, с информационной системой 1С 7.7 и использовано при автоматизации оперативного планирования производства с учетом характерных для конкретных предприятий критериев и ограничений. Архитектура предложенного решения поддерживает большинство промышленных платформ: UNIX, Linux, WIN NT, а также позволяет осуществлять интеграцию с прочими корпоративными информационными системами.

Внедрение и реализация результатов. Результаты исследований, проведенных в диссертационной работе, были внедрены на отечественных предприятиях ОАО «Лебедянский», ЗАО «ФМРус» и ЗАО НПО «Тяжпромарматура», а также использованы в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана.

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

Апробация работы. Основные результаты работы докладывались на: Международной научно-технической конференции студентов и аспирантов

Радиоэлектроника^ электротехника и энергетика» (Москва, ,2002г.), Научной сессии МИФИ-2002 (Москва, 2002г.), П-м Международном научно-практическом семинаре «Интегрированные - модели и мягкие вычисления в искусственном интеллекте». (Коломна,. 2003г.), Международных, научно-технических конференциях IEEE AIS'03 и САВ-2003 (Дивноморское; 2003г.), Международных научно-технических конференциях: IEEE AIS'04. и CAD-2004 (Дивноморское, 2004г.),. Ш-м; Международном; научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном-интеллекте»; (Коломна, 2005г.), практическом семинаре «Решения ORACLE для- пищевой; промышленности» - (Москва;. 2007г.); IV—й? Международной; научно-практической конференции' «Интегрированные модели и мягкие вычисления: в искусственном' интеллекте». (Коломна;. 2007г.), VI-ш Международной! научно-практической конференции «Интегрированные, модели и мягкие вычисления;: в искусственном интеллекте». (Коломна, 2011г.), а также на Всероссийской^ конференции «Эффективные методы автоматизации технологической подготовки и планирования' производства»-(Москва, 2011г.)

На защиту выносятся: '

1. Модель оперативного планирования производства, как системы адаптации?искусственнь1Х агентов, использующих теорию» анимата и? метод обучения с подкреплением. ;

2. Схема каскадного взаимодействия агентов для: устранения ресурсных конфликтов и нарушений ограничений в ходе поискового процесса.

3. Модифицированные генетические операторы кроссинговера и мутации, снабженные экспертными правилами? относительно предмета решаемой задачи.

4. Гибридный алгоритм оперативного планирования на основе модифицированного генетического алгоритма и алгоритма адаптации.

Основные выводы и результаты

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

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

2. Решена задача планирования загрузки поточных линий? в условиях цеховых ограничений. Разработаны алгоритм многоагентного планирования и модифицированный генетический алгоритм, позволяющие учитывать организационно-технологическую специфику при создании оперативного плана производства. Построенные модели каскадного взаимодействия, агентов и модифицированные генетические операторы, позволили значительно (в среднем на 20%) сократить фактическое время, требуемое для получения/ приемлемого варианта плана, удовлетворяющего ограничениям.

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

4. Разработана программная архитектура системы оперативного планирования, опирающаяся на подходы технологии «тонкого» клиента при работе в гетерогенных программных средах. Архитектура предложенного решения поддерживает большинство промышленных платформ: UNIX, Linux, WIN NT, а также позволяет осуществлять интеграцию с прочими корпоративными информационными системами.

5. Внедрение разработанных методов, алгоритмов и программных средств на промышленных площадках ОАО «Лебедянский» и ЗАО «ФМРус» позволило снизить фактическое время, затрачиваемое плановиком на подготовку оперативного плана, от нескольких часов до получаса. Впервые удалось уйти от так называемых «интуитивных» оценок качества плана и применить количественную оценку.

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

1. Анохин К.В., Жданов A.A., Зарайская И.Ю. Исследование формирования поведенческих стратегий в биолого-кибернетических, экспериментах// Сбь научн. тр. Всероссийской научно-технической., конференции Нейроинформатика-2007. — Mi, 2007. — С.76-84.

2. Аоки М. Введение в методы оптимизации: Пер. с англ. -М.:Наука, 1977. -343с. •.'. .

3. Афонин; П.В. Гибридные системы интеллектуального < имитационного моделирования на основе бионических подходов и многоагентных моделей: дисс. канд.гехн.наук. Москва., 2005. — 209 с.

4. Беккер И, Вилков Ji., Таратухин В.В. Менеджмент процессов. М.: Эксмо, 2008. - 384с.

5. Блишун А.Ф., Тарасов В.Б., Теплицкий. Б.Е. Проблемы построения экспертной системы планирования работ в особых условиях// Проблемыприменения экспертных систем в народном хозяйстве. — Кишинев, 1989. -С.34-37.

6. Бром А.Е., Колобов A.A., Омельченко И.Н. Интегрированная логистическая поддержка жизненного цикла наукоемкой продукции. — М.: Изд-во МГТУ им.Н.Э.Баумана, 2008. 296с.

7. Бурков В.Н., Новиков Д.А. Как управлять проектами. М.: СИНТЕГ, 1997.- 188с.

8. Вагнер Г. Основы исследования операций -М.: Мир, 1972.— Т.1 — 336с.

9. Вагнер Г. Основы исследования операций -М.: Мир, 1972. — Т.2 — 487с.

10. Вагнер Г. Основы исследования операций -М.: Мир, 1972. — Т.З — 503с.

11. Варшавский В:А., Поспелов Д.А. Оркестр играет без дирижера. Размышления об эволюции некоторых технических систем и управлении ими. -М.: Либроком, 2009. 234с.

12. Вебер Ю., Гельдель X., Шеффер У. Организация стратегического и оперативного планирования на предприятии// Проблемы теории и практики управления. 1998. —№2. - С.105-110.

13. Виттих В.А. Эволюционное управление сложными системами // Известия Самарского научного центра РАН. 2000. - Т.2, №1. - С.53-65.

14. Виттих В.А., Скобелев П.О. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах// Автоматика и телемеханика. 2003. — №1. — С.177-185.

15. Вумек Дж. П., Джонс Д. Т. Бережливое производство. Как избавиться от потерь и добиться процветания вашей компании. — М.: Апьпина Бизнес Букс, 2008:-264с.

16. Высочин C.B., Пителинский К.В., Смирнов Ю.Н. Принципы построения систем для расчета производственных расписаний// САПР и графика. -2008. №9. - С.57-59.

17. Гаврилов : A.B. Гибридные интеллектуальные системы. Новосибирск: Изд-во НГТУ, 2003. - 168 с.

18. Гаврилов Д.А. Управление производством на базе стандарта MRP II. — СПб: Питер, 2002. -320 с.

19. Гаврилова Т.А., Муромцев Д.И. Интеллектуальные технологии вменеджменте.—СПб:Изд-во «Высшая школа менеджмента», 2008. — 487с.

20. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. СПб: Питер, 2000. - 384 с.

21. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ. — М.: Мир, 1985. 509 с.

22. Гладков JI.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы2.е изд., испр. и доп.)/ Под ред. В.М. Курейчика. — М.: Физматлит, 2006. 320 с.

23. Гладков JI.A., Курейчик В.В., Курейчик В.М. Биоинспирированные методы в оптимизации. — М.: Физматлит, 2009. — 384 с.

24. Громов С.А. Методы адаптивного и генетического поиска в оперативном планировании производства// Известия высших учебных заведений. Машиностроение. 2011.- №8. - С.74-80.

25. Громов С.А., Тарасов В.Б. Методы искусственного интеллекта в автоматизации оперативного планирования// Программные продукты и системы. 2007. - №4. - С.89-92.

26. Громов С.А., Тарасов В.Б. Интегрированные интеллектуальные системы оперативного планирования производства// Известия Южного федерального университета. Технические науки. — 2011. — №7. — С.60-67.

27. Громов С.А. Решение задачи загрузки оборудования с помощью алгоритма коллективной адаптации// Интеллектуальные системы и технологии: Научная сессия МИФИ-2002: Сборник научных трудов; В 14-и томах. М.,2002. - Т.З. - С. 196-198.

28. Громов С.А. Возможности использования ERP-системы для поддержки оперативного планирования производства// Chief Information Officer — руководитель информационной службы. М., 2006. - № 9 (52). - С.44-49.

29. Громов С.А. Интеллектуализация систем оперативного планирования производства// Сборник, трудов VI-й Международной научно-практической конференции (г.Коломна), 16-19 мая 2011 г. М., 2011. -Т.2. - С.588-598.

30. Гэри М., Джонсона Д. Вычислительные машины и труднорешаемые задачи: Шер: с англ.,-М.: Мир; 19821- 416с.

31. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практикаэволюционного моделирования; М.: Физматлит, 2003. - 462с.

32. Емельянов В.В., Ясиновский С.И. Гибридная система для планирования производства на основе генетических алгоритмов, методов имитации и экспертных систем// Известия ТРТУ. 1996. - №3. - С.4-9.

33. Емельянов В.В., Ясиновский С.И. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО. -М.: АНВИК, 1998.-427с.164 .

34. Основы построения мультиагентных систем: Учебное пособие / В.В.Андреев, И.А.Минаков, В .В .Пшенични ков, Е.В.Симонова и др. -Самара: ПГАТИ, 2007. 151с.

35. От моделей; поведения к искусственному интеллекту/ Под ред. В.Г.Редько. М.: КомКнига, 2006. - 447с.

36. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация;, Алгоритмы ^ сложность: Пер. с англ.-М;: Мир, 1982. 510с.

37. Первозванский А.А. Математические модели в управлении производством.-М.: Наука, 1975.- 615с.

38. Попов Э.В., Фоминых И.Б., Кисель Е.Б. Статические и динамические экспертные системы: Учебное пособие. — М.: Финансы и статистика; 1996. 320с.

39. Поспелов? Г.С. 'Искусственный интеллект основа новой; информационной технологии: — Mi:Наука; 19i88. — 280с:

40. Поспелов Д.А. Многоагентные системы настоящее и будущее // Информационные технологии и вычислительные' системы. — 1998: — №1.-С. 14-21.

41. Рассел- С., Норвиг П. • Искусственные; интеллект: современный; подход, 2-е изд.: Пер.с англ. М.: Издательский дом «Вильяме», 2006. — 1408с.88: Растригин J1.A. Адаптация сложных систем Рига: Зинатне, 1981. - 375с.

42. Редько ВЭволюционная кибернетика. — М.: Наука, 2001.-156с.

43. Редько 'В.Г. Модели адаптивного поведения// Труды Международных технических конференций IEEE AIS' 03 и CAD-2003, (г.Дивноморск), 310 сентября 2003.-М., 2003. Т. 1 - С. 255-267.

44. Редько В.Г., Прохоров Д.В. Нейросетевые адаптивые критики// Научная сессия МИФИ-2004. VI Всероссийская научно-техническая конференция? Нейроинформатика 2004: Сборник научных трудов; М.: МИФИ, 2004.• Ч.2.- С.77-84.

45. Рыбина. F.B. Основы построения интеллектуальных систем: учеб. пособие -М.: Финансы и статистика, 2010. -432с.

46. Тарасов В.Б. От искусственного интеллекта к искусственной жизни: новые направления в науках об искусственном// Новости искусственного интеллекта. 1995. - №4. - С.93-117.

47. Тарасов В.Б. Новые стратегии реорганизации и автоматизации предприятий: на пути к интеллектуальным предприятиям// Новости искусственного интеллекта. 1996. - №4. - С.40-84.

48. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: Эдиториал УРСС, 2002. - 352с. (Науки об искусственном.).

49. Тарасов В.Б., Голубин A.B. Эволюционное проектирование: на границе между проектированием и самоорганизацией// Известия ТРТУ. Тематический выпуск Интеллектуальные САПР. 2006. — №8(63). — С.77-82.

50. Тельнов Ю.Ф. Интеллектуальные информационные системы вэкономике. М.: СИНТЕГ, 2002. - 316с.

51. Taxa Хэмди А. Введение в исследование операций. 6-е издУПер. с англ.-М.: Вильяме, 2001. 912с.

52. Теория расписаний и вычислительные машины/ Под ред. Э.Г. Коффмана. М.: Наука, 1984. - 334с.

53. Третьяков Э.А.,Игнатова Л.А. Автоматизированные системы управления производством. -М: Машиностроение, 1991. 96 с.

54. Уоллас Т., Сталь Р. Планирование продаж и операций. Практическое руководство: Пер. с англ. 3-е изд. СПб.: Питер, 2009. - 272с.

55. Управление жизненным циклом продукции/ А.Ф.Колчин,I

56. М.В.Овсянников, А.Ф.Стрекалов, С.В.Сумароков. М.: Анахарсис, 2002. - 304с.

57. Фролов Е.Б., Загидуллин P.P. MES-системы как они есть или Эволюция систем планирования производства // Генеральный директор. — 2008. — №4.-С. 84-91.

58. Фролов Е.Б., Загидуллин P.P. Оперативно-календарное планирование и диспетчирование в MES-системах // Станочный парк. 2008. — № 11. — С.22-27.

59. Хоботов E.H. Организационно-техническое управление. Курс лекций. -М.:Изд-во МГТУ им.Н.Э.Баумана, 2003. 4.2- 74с.

60. Хоботов E.H. О некоторых моделях и методах решения задач планирования в дискретных производствах// Автоматика и телемеханика. 2007. - №12. - С. 85-100.

61. Хоботов E.H. Агрегирование в задачах планирования и построения расписаний// Труды VI-й Московской международной конференции по исследованию операций — М., 2010. — С.315-317.

62. Цетлин M.JI. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969. — 316 с.

63. Шапиро Дж. Моделирование цепи поставок: Пер. с англ.- СПб.: Питер, 2006. — 720 с. (Серия «Теория менеджмента»).

64. Ярушкина Н.Г. Основы теории нечетких и гибридных систем. — М.: Финансы и статистика, 2004. — 320 с.

65. SAP ERP. Построение эффективной системы управления: Пер. с англ. -М.: Альпина бизнес букс, 2008. — 346 с.

66. Advanced Planning and Scheduling Solutions in Process Industry/ Ed. by H.-O. Günther. Berlin: Springer-Verlag, 2003. - 426p.

67. Bagchi T.P. Multiobjective Scheduling by Genetic Algorithms. — Boston: Kluwer Academic Publishers, 1999. 183p.

68. Brucker P. Scheduling Algorithms. -Berlin: Springer-Verlag, 2001. -365p.

69. Brucker P., Knust S. Complex Scheduling. -Berlin: Springer-Verlag, 2006. -285p.

70. Davis L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991.-384p.

71. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison-Wesley Publishing Company Inc., 1989. -432p.

72. Graves S.C. A Review of Production Scheduling// Operations Research. — 1981.-Vol.29. -P.646-676.

73. Hall N.G., Potts C.N. Supply Chain Scheduling: Batching and Delivery // Operations Research. -2003. Vol. 51. -P.566-584.

74. Handbook of Scheduling: Algorithms, Models and Performance Analysis. /Ed. by J:Y.-T. Leung. Boca Raton (Florida): Chapman & Hall/CRC, 2004. - 1216p.

75. Herrmann J., Lee C.-Y., Snowdon J. A Classification of Static Scheduling Problems// Complexity in Numerical Optimization/ Ed. by P. M. Pardalos. -Singapore: World Scientific, 1993. -P.203-253.

76. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with »Application to Biology, Control and Artificial Intelligence. -Ann Arbor: University of Michigan Press, 1975. 21 lp.'

77. Jain A.S., Meeran S. Deterministic Job-Shop Scheduling: Past, Present and Future// European Journal of Operational Research. — 1999. —Vol.113. -P.390-434.

78. Kerzner H. Project Management: A Systems Approach to Planning, Scheduling and Controlling, Fifth Edition. New York: Van Nostrand Reinhold, 1994. - 1152p.

79. Kirkpatrick S., Gelatt C.D., Vecchi M.P. Optimization by Simulated Annealing// Science. 1983. -Vol. 220: -P.671-680.

80. Kusiak A., Chen M. Expert Systems for- Planning and» Scheduling . Manufacturing Systems// European Journal of Operational Research. 1988.-Vol. 34. —P.113-130.

81. Manufacturing Execution Systems (MES)/; Edr.by» JÎ Kletti. --- Berlin -Heidelberg: Springer-Verlag, 2007. 885p.

82. Miller T.C. Hierarchical Operations and Supply Chain Planning.- London: Springer Verlag; 2002. 265p.

83. Morton Т.Е., Pentico D: Heuristic Scheduling Systems. New York: John Wiley and Sons, 1993. - 720p.

84. Noronha S.J., Sarma V.V.S. Knowledge-Based Approaches for Scheduling Problems: a Survey// IEEE Transactions on Knowledge and Data Engineering. 1991. -Vol. 3.-P.160-171.

85. ORACLE Applications Implementation Method: Redwood Shores: Oracle University, 2005. - 855p. '

86. ORTEMS ; System ; Documentationi — Lyon : ORTEMS' Pre s s j 2009^ — p. 1025.

87. Parker R.G. Deterministic Scheduling Theory.-London: Chapman & Hall, 1995.-296p;148i Pinedo M.L. Scheduling Theory, Algorithms, and Systems, 2 ed. - Upper Saddle River, New; Jërsey: Prentice-Hall, 2002. - 586p.

88. Pinedo M.L. Planning and Scheduling in Manufacturing and Services, 2nd ed. Heidelberg: Springer Verlag, 2009. - 537p.

89. Pinson. E. The Job Shop Scheduling Problem: A Concise Survey and Some Recent Developments. Scheduling Theory and its Applications/ Ed. by

90. Ph.Chretienne, E.G. Coffman, J.K. Lenstra, Z. Liu. New York: John Wiley and Sons, 1995. - P. 177-293.

91. Potts C.N., van Wassenhove L.N. Algorithms for Scheduling a Single Machine to Minimize the Weighted Number of Late Jobs// Management Science. -1988. Vol.34. -P.843-858.

92. Rachamadugu R., Stecke K.E. Classification and Review of FMS Scheduling-Procedures// Production Planning and Control. -1994. Vol. 5. - P.2-20.

93. Rodammer F.A. White K.P. A Recent Survey of Production Scheduling // IEEE Transactions on Systems, Man and Cybernetics. 1988. - Vol.18. -P.841-851.

94. Shaw M.J.P., Whinston A.B. An Artificial Intelligence Approach to the Scheduling of Flexible Manufacturing Systems// HE Transactions. -1989. — Vol.21.-P.170-183.

95. Shingo S. Study of Toyota Production System from Industrial Engineering Viewpoint Tokyo: Nihon Noritsu Kyokai (Japan Management Association), 1982.-258p.

96. Smith S.F., Fox M.S., Ow P.S. Constructing and Maintaining Detailed Production Plans: Investigations into the Development' of Knowledge-Based Factory Scheduling Systems// AD Magazine. 1986. - Vol.7. -P.45-61.

97. Sutton R., Barto A. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998.-342p.

98. Vaessens R.J.M., Aarts E.H.L., Lenstra J.K. Job Shop Scheduling by Local Search// INFORMS Journal on Computing. 1996. - Vol.8. - P.302-317.

99. Vieira G.E., Herrmann J.W., Lin E. Rescheduling Manufacturing Systems: A Framework of Strategies, Policies and Methods// Journal of Scheduling. — 2003.-Vol.6.-P.39-62.

100. Wu S.D., By eon S.E, Storer R.H. A Graph-Theoretic Decomposition of Job

101. Shop Scheduling Problems to Achieve Schedule Robustness// Operations Research. -1999. Vol. 47. -P. 113-124.

102. ZadehL.A. Fuzzy Sets//Information and Control.- 1965.-Vol.8.-P.338-353.