Содержание к диссертации
Введение
ГЛАВА 1. Проблемы анализа и оптимизации процессов преобразования ресурсов 10
1.1 Процессы преобразования ресурсов 10
1.1.1 Понятие прогресса преобразования ресурсов 10
1.1.2 Примеры процессов преобразования ресурсов 11
1.2 Основные задачи анализа и оптимизации дискретных ППР 16
1.2.1 Задачи анализа 16
1.2.2 Задачи синтеза и управления ППР 17
1.3 Обзор существующих инструментов описания, анализа, оптимизации и управления ППР 21
1.3.1 Универсальные средства имитационного моделирования 21
1.3.2 Средства управления производством и оптимизации производственных процессов 25
1.3.3 Мультиагентный подход к планированию распределения ресурсов и средств 31
1.4 Математические методы оптимизации распределения ресурсов 33
1.4.1 Точные математические методы 33
1.4.2 Эвристические методы 36
1.5 Проблема и ее решение 37
Выводы 39
ГЛАВА 2. Структура и математическое описание системы преобразования ресурсов 40
2.1 Классификация процессов преобразования ресурсов 40
2.2 Математическая модель ппр 50
2.3 Математические модели преобразователей ресурсов 52
2.3.1 Пассивные преобразователи ресурсов 53
2.3.2 Активные преобразователи ресурсов 57
2.3.3 Модель парка средств 64
2.3.4 Модель хранилища ресурса 67
2.3.5 Поток ресурсов и средств 68
2.3.6 Информационный поток 68
2.4 Формализация критериев качества планирования 69
2.5 Машина вывода 76
Выводы 78
ГЛАВА 3. Принципы построения пакета моделирования и управления процессами преобразования ресурсов . 79
3.1 Онтологический подход к моделированию ППР 79
3.2 Функциональные возможности пакета 82
3.3 Принципы построения системы сбора, хранения и предоставления информации 85
3.3.1 Принципы работы с системой 85
3.3.2 Внутренний математический аппарат подсистемы 88
3.3.3 Информационное обеспечение 91
3.4 Подсистема моделирования ППР 92
3.4.1 Агентский подход к моделированию ППР 93
3.4.2 Алгоритмическое обеспечение 95
3.5 Технология работы с пакетом анализа и оптимизации ППР 100
Выводы 105
ГЛАВА 4. Решение задач анализа и планирования 106
4.1 Задачи анализа 106
4.2 Задачи планирования 117
4.2.1 Контрольный пример построения плана распределения ресурсов . 117
4.2.2 Составление производственного плана для изделия СБ.8000 128
Выводы 134
Заключение 135
- Примеры процессов преобразования ресурсов
- Классификация процессов преобразования ресурсов
- Онтологический подход к моделированию ППР
- Контрольный пример построения плана распределения ресурсов
Введение к работе
Актуальность темы. Данная работа посвящена вопросам анализа и оптимизации дискретных процессов преобразования ресурсов (ППР). Примерами систем преобразования ресурсов могут служить производственные процессы снабжения, изготовления и сбыта продуктов, логистические цепочки поставок ресурсов и т.д. Неизбежным следствием ошибок при распределении ресурсов становятся: увеличение времени выпуска продукта (выполнения заказов), увеличение себестоимости, рост объема хранимого ресурса, срыв сроков поставок. Понимание этого факта привело к повышению интереса к задачам анализа, планирования, диспетчирования и поиска эффективных структур процессов преобразования ресурсов. Особую роль здесь играет вопрос обучения будущих специалистов современным подходам к управлению процессами преобразования ресурсов.
Указанные задачи оптимизации распределения ресурсов (средств) и проектирования новых ППР относятся к классу сложных I систем - являются комбинаторными задачами большой размерности (с математической точки зрения задача является NP-полной). Для их решения применяются различного рода эвристики. Значительный интерес для решения данных задач представляет исследование возможности применения мультиагентного подхода к моделированию поведения автономных объектов с целью разделения общей задачи оптимизации на ряд частных подзадач, решаемых в рамках отдельных агентов, и получения согласованных и эффективных планов совместной работы агентов за ограниченное время.
Еще одной задачей внедрения математических методов анализа и синтеза ППР
является их адаптация к конкретной предметной области. В этом плане для решения
этой задачи представляет интерес использование онтологического подхода,
реализующего последовательное уточнение понятий предметно^ области от наиболее
абстрактных понятий к конкретным. і
В этой связи разработка математических методов и информационной системы,
обеспечивающей эффективное решение задач анализа и синтеза ППР на основе
совместного использования онтологических методов описания, мультиагентного
пооперационного моделирования и оптимизации дискретных процессов преобразования
ресурсов, является актуальной. !
Целью работы является разработка математического и алгоритмического обеспечения, реализующего повышение качества анализа процессов, планирования работ, распределения ограниченных средств и ресурсов при управлении дискретными процессами преобразования ресурсов.
Исходя из цели исследования, определены основные задачи:
-
Выполнить сравнительный анализ универсальных пакетов имитационного моделирования ППР и специализированных средств управления и планирования производственных процессов, установить их достоинства и недостатки для моделирования дискретных ППР.
-
Выполнить анализ математических моделей, применяемых при решении задач построения расписаний распределения ограниченного набора ресурсов.
-
Разработать математические модели ППР и их элементов, учитывающие конфликты на ресурсах и целевые установки как всего процесса, так и отдельных элементов. |
-
Разработать алгоритмическое обеспечение для реализации мультиагентного подхода моделирования процессов преобразования ресурсов.
5. Разработать инструментальное программное средство для поддержки
онтологического описания моделей, проведения имитационных
экспериментов, анализа результатов и оптимизации ППР.
і
Методы исследования. Для решения поставленных задач используются методы
системного анализа и [синтеза, методы ситуационного управления и имитационногр
моделирования, аппарат продукционных систем, теория расписаний, теория и методы
принятия решений, онтологический подход к построению баз знаний предметных
областей. I
Научная новизна решения поставленных задач заключается в следующем: 1. Предложен комплексный подход описания дискретных ППР, их анализа и
оптимизации, объединяющий онтологический подход, аппарат ситуационного
и мультиагентного моделирования. .
2. Разработаны (математические модели элементов ППР на основе аппарата
продукционных систем, учитывающие интересы отдельных элементов при
формировании плана преобразования ресурсов.
-
Разработаны нотация и метаязык описания моделей процессов преобразования ресурсов.
-
Разработано алгоритмическое обеспечение (алгоритм формирования модели процесса, алгоритмы поведения элементов модели, алгоритм проведения вычислительного эксперимента), обеспечивающее минимизацию вычислительных затрат и мультиагентное моделирование ППР в условиях ограниченности ресурсов.
I Практическая значимость работы. Разработанные математические модели процессов, учитывающие конфликты на ресурсах и целевые установки, как всего процесса, так и отдельных элементов, онтологический подход к описанию ППР, алгоритмическое обеспечение и пакет прикладных программ обеспечивают повышение: качество анализа процессов, планирования работ, распределения ограниченных ресурсов и средств при управлении дискретными процессами преобразования ресурсов.
На защиту выносятся следующие результаты исследований:
-
Математические модели пассивных и активных процессов преобразования ресурсов, обеспечивающие проведение анализа и оптимизацию построения планов преобразования ресурсов с учетом ограничений на ресурсы преобразования,
-
Онтологическая система описания процессов преобразования ресурсов, позволяющая концептуально моделировать ППР путем последовательного анализа и структурирования имеющихся данных об объекте моделирования.
-
Алгоритмы мультиагентного моделирования процессов распределения ресурсов (алгоритм генерации мультиагентной имитационной модели на основе статической онтологической модели процесса, алгоритмы поведения активных' элементов).
Реализация результатов работы. Разработанное в диссертации программное обеспечение используется в учебном процессе Радиотехнического института Уральского государственного технического университета - УПИ. Результаты работы использованы компанией ЗАО «Микротест» при разработке технической концепции
построения корпоративной информационной системы ООО «КАМАЗавтотехник». Созданный инструмент онтологического моделирования апробирован на проектах, проводимых ЗАО «Институт программных систем». Внедрение экспериментальной версии системы анализа и оптимизации ППР , осуществлено в компании ЗАО «Уральский завод эластомерных уплотнений».
Реализация результатов работы подтверждается соответствующими актами.
I Апробация работы. Основные положения и результаты исследований
диссертации докладывались автором на следующих международных, всероссийских,
отраслевых и региональных конференциях и семинарах:
Международная научно-практическая конференция «СВЯЗЬ-ПРОМП 2006» в рамках III Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2006» (Екатеринбург, 2006); |
Международная научно-практическая конференция «СВ^ІЗЬ-ПРОМП 2005» в рамках II Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2005» (Екатеринбург, 2005); I
молодых ученых ГОУ ВПО УГТУ-УПИ
VII отчетной конференции
молодых ученых ГОУ молодых ученых ГОУ
(Екатеринбург, 2005);
ВПО УГТУ-УПИ
VI отчетной конференции
(Екатеринбург, 2004);
ВПО УГТУ-УПИ
V отчетной конференции
(Екатеринбург, 2003).
Публикации. По теме диссертации опубликовано 11 научных работ, в том числе 9 печатных трудов в тематических сборниках и трудах научно-технических конференций российского и международного значения, из них 3 работы в рецензируемых изданиях,
рекомендуемых ВАК. !
Структура и объем работы. Диссертация состоит из введения, четырех глав,
заключения, списка литературы (117 наименований) и приложения. Объем основной
части работы - 170 страницы, 66 рисунков, 19 таблиц. !
Примеры процессов преобразования ресурсов
В качестве примеров систем преобразования ресурсов могут быть представлены бизнес-процессы на уровне всего предприятия, внутренние производственные процессы, цепочки поставок в логистике, обработка документов и т.п. [31, 39, 41, 54, 57].
При описании деятельности предприятия часто используются понятия бизнес-процесса и производственного процесса, которые по своей сути являются процессами преобразования ресурсов. В обобщенном виде предприятие может быть представлено следующей схемой преобразования ресурсов (рисунок 1.1). Как видно предприятие представляет сложную систему с обратными связями, в рамках которой реализуются следующие подпроцессы: снабжение - процесс взаимодействия с внешней средой, приводящий к уменьшению денежных средств на счете предприятия и пополнению склада ресурсов; производство - процесс преобразования входных ресурсов в готовую продукцию с использованием оборудования и персонала; сбыт - процесс взаимодействия с внешней средой, приводящий к уменьшению готовой продукции на складе, увеличению денежных средств на счете предприятия, получению прибыли и соответственно к выплате налогов; Для подробного изучения и анализа ППР создаются модели внутренних процессов путем декомпозиции процессов верхнего уровня. Тем самым создается иерархическая-многоуровневая модель процесса. На нижних уровнях достигается детализация в рамках выполняемых операций. Более подробно вопросы создания моделей сложных многоуровневых иерархических процессов рассмотрены в [1, 14, 33, 56]. Выделяют следующие типы производственных процессов [17, 37]: поточное производство (flow shop); производство на заказ (job shop). При поточном производстве продукции определенного типа имеет место один технологический маршрут, подразумевающий одинаковую последовательность производственных операций. Организация производства (расположение машин, рабочих столов, сборочных линий и т.д.) спроектирована так, чтобы способствовать движению «потока» продуктов, минимизировать манипуляции с материалами и комплектующими. Производство работает в определенном темпе и продукты обычно производятся «на объем». При этом оборудование производственной линии часто узко специализировано для производства одного типа продукции. Управление запасами подчинено ритму работы производственной линии. Критическим является отсутствие материалов и комплектующих. Поточное производство часто называют массовым производством, или говорят, что имеется непрерывная организация производства. Примерами дискретного поточного производства могут служить производство бытовой электроники, металлургические производства. Производство на заказ При данном типе производства в центре внимания оказывается не технологический процесс, как в случае с поточным производством, а заказ. Наиболее характерными чертами производства на заказ являются следующие [17]: универсальное оборудование может быть настроено на выполнение различных технологических операций; происходит группирование сходного по функциям оборудования в так называемые рабочие центры; производимая продукция изготавливается по заказам и одновременно идет обработка многих заказов; для управления производством необходима подробная информация о заказах и рабочих центрах, включая, например, сведения о последовательности обработки заказов на рабочих центрах, определение приоритета заказов, потребности каждого заказа во временных ресурсах, знание состояния выполняемых заказов, производственной мощности рабочих центров, потребности в производственных мощностях для критических рабочих центров; необходимо координировать планирование заказов и наличие необходимых ресурсов (материала, персонала, инструментального обеспечения). При позаказном производстве необходимо отслеживать исполнение плана и отклонения, как в разрезе заказов, так и в разрезе рабочих центров (машин, рабочих). Типичной проблемой, с которой здесь можно столкнуться, может быть неравномерность загрузки различных рабочих центров. Таким образом, сложно без специального инструментария управляться с сотнями производственных заказов, ежедневно проходящих через предприятие.
Классификация процессов преобразования ресурсов
Для описания сложный процесс обычно расчленяют на составляющие с целью подбора готовых математических схем или разработки оригинальных. Разделение процесса на операции не является однозначным, т.к. может быть выполнено многими способами. В связи с этим возникает проблема выбора наиболее удачного варианта совокупности типов элементов, описывающих процесс. Указанная проблема в общем виде в настоящее время не решена. Н.П. Бусленко в работе [11] рекомендует выделять элементы по функциональности.
В рассматриваемых предметных областях ППР реализуются процессы производства ресурса, хранения ресурсов и аренды средств производства. Производство предусматривает преобразование входного(ых) ресурса(ов) в выходной продукт, хранение, прием и передачу ресурсов, предоставление средств производства для осуществления преобразования ресурсов. В соответствии с этим должны быть выделены функциональные элементы, описывающие модель процесса ППР. Также должен быть реализован механизм адаптации элементов к конкретным особенностям процесса, позволяющий уточнять их функциональные возможности в рамках базовых.
В данной работе процесс преобразования ресурсов представляется в виде графа, узлами которого являются преобразователи ресурса, хранилища ресурсов и парки средств, а дуги - материальные и информационные потоки. В общем случае, преобразователь представляет собой временное отношение между входным потоком ресурсов, выходным потоком ресурсов и средствами преобразования (парком средств). Входной и выходной поток ресурсов преобразователя характеризуется количеством ресурса. В зависимости от того, чем определяется данное отношение, все множество процессов преобразования ресурсов делится на следующие классы [27]: пассивные процессы, активные процессы, смешанные процессы.
В пассивных процессах ресурсный поток, возникающий между преобразователями, обусловлен текущим состоянием ресурсов на входах и выходах преобразователей, а также назначенными правилами и планами использования средств. Таким образом, пассивные объекты управляются только внешним окружением. Примером пассивного процесса является процесс массового изготовления продукции при заданном объеме сырья, компонент и фиксированной технологии изготовления (см. раздел 1.1.2).
Преобразователи активных процессов могут самостоятельно оптимизировать свою деятельность в соответствии с заданными критериями. При этом в зависимости от того предшествует ли выполнению ППР процесс согласования распределения средств и поставок ресурсов процессу изготовления продукта или нет, активные процессы подразделяются на активные процессы с предварительным согласованием планов и активные процессы с планированием в ходе исполнения. В активных процессах с согласованием планов преобразователи предварительно обмениваются друг с другом информационными сообщениями, с помощью которых согласуются объемные и временные характеристики ресурсных потоков, а также расписание использования средств производства.
Процессы смешанного типа включают как активные, так и пассивные преобразователи. Часть подпроцессов в них функционирует по внешним заявкам, а другая часть протекает безусловно и определяется первыми.
В составе пассивных процессов по функциональному предназначению выделены следующие элементы: пассивные преобразователи (ПП); пассивные хранилища ресурсов (ПХ); пассивный парк средств (ПС); поток ресурсов; поток средств. В состав активных процессов входят: активные преобразователи (АП); активные хранилища ресурсов (АХ); активный парк средств (АС); информационный поток; поток ресурсов; поток средств. В рамках данной работы все элементы предлагается рассматривать как агентов, действующих в рамках ППР.
Пассивные преобразователи являются основными структурными элементами пассивных процессов. Данные объекты осуществляют «безусловную» трансформацию входного ресурса в выходной при наличии необходимого количества ресурсов на входе преобразователя, свободных средств и свободного места во внутреннем выходном буфере. Пассивный преобразователь описывается: функцией преобразования; набором входных и выходных ресурсов и объемами внутренних буферов по каждому ресурсу; перечнем средств, необходимых для выполнения преобразования; «обменным ресурсом» и механизмом эквивалентного обмена.
При поступлении всех входных ресурсов на вход и наличии свободного места во внутреннем выходном буфере продукта преобразователь создает выходной продукт, который поступает на вход следующему по цепочке преобразователю или во внутренний буфер продукта. ПП не может начать очередной цикл преобразования ресурсов, если выходной буфер заполнен. Особым, представляющим интерес, случаем преобразователя является преобразователь с нулевыми буферами.
В ПП отдельно выделяется обменный ресурс и буфер обменного ресурса. Данным ресурсом осуществляется «оплата» поставок входных ресурсов и данный ресурс взимается с потребителей за выходной продукт. Графическое обозначение ПП приведено на рисунке 2.1.
Онтологический подход к моделированию ППР
Изложенная в главе 2, математическая модель использована при построении системы моделирования и управления процессами преобразования ресурсов.
Для описания номенклатуры и реквизитов всевозможных ресурсов, участвующих в ППР, взаимосвязей между понятиями, потоков ресурсов, информационно-управляющих потоков, а также правил преобразования необходим некоторый механизм. Решения подобных вопросов в специфических задачах хранения и доступа к данным были предложены в технологиях баз данных (концептуальное моделирование ПрО) [47, 76]. Но на общем поле разработки систем, основанных на знаниях, с середины 90-х годов начинает доминировать подход, связанный с использованием явных онтологии содержания ПрО [6, 15, 50, 70, 71, 79].
Онтология - формальное явное описание понятий (классов) в рассматриваемой предметной области, свойств каждого понятия (слотов), описывающих различные характеристики, и ограничений, наложенных на понятия (фацетов, аксиом). В любой системе существует две основные категории предметов восприятия, такие как сами объекты, составляющие систему (физические и интеллектуальные) и взаимосвязи между этими объектами. В терминах онтологии, понятие взаимосвязи является точным дескриптором зависимости между объектами системы в реальном мире, а термины - являются, соответственно, точными дескрипторами самих реальных объектов. Онтология вместе с набором индивидуальных экземпляров классов образует базу знаний ПрО.
Согласно [49] схема, отражающая состав и взаимосвязи основных фаз технологии моделирования с использование онтологии, реализуемая при создании предметно-ориентированных сред компьютерного моделирования в частности моделирования производственных ППР и проведении вычислительных экспериментов, имеет следующий вид (рисунок 3.1).
В соответствии со схемой онтология, как концептуальная модель предметной области (ПрО), связана с анализом и структурированием имеющихся данных о предприятии. Существует возможность создания нескольких различных концептуальных моделей-онтологий для данной ПрО.
Результатом объектного моделирования является отражение, воспроизведение, описание конкретного объекта или системы объектов Пр выполненное в рамках избранной онтологии. В рамках объектного описания специфицируются знания о «вычислениях». Таким образом, фазу можно рассматривать как спецификацию процесса решения задачи, описания воздействий на стартовую объектную модель, в результате которых она приобретает некоторые удовлетворяющие проектировщика свойства.
Последней фазой является проведение вычислительного эксперимента. При этом реализуются (интерпретируются виртуальной машиной) знания о возможных трансформациях модели, другими словами осуществляется имитационное моделирование.
В настоящее время для создания и поддержки онтологии существует целый ряд инструментов [36, 48, 81, 90]. В подавляющем большинстве работ по использованию явных онтологии в системах, основанных на знаниях, для построения онтологии применяется или рекомендуется объектно-фреймовый стиль представления знаний. Большинство из рассмотренных инструментальных средств разрабатываются университетскими исследовательскими группами, поэтому являются либо открытым кодом, либо предлагают свободный доступ к своим функциям.
В таблице 3.1 представлены характеристики ряда современных инструментов построения онтологии: Protege, Ontolingua, OntoEdit, OilEd, Visio for Enterprise Architets. Часть из этих редакторов онтологии доступна как независимые приложения, другие как плагины или web-сервисы.
Данные программы имеют развитые средства описания таксономии объектов, правил взаимодействия между объектами, но в них не предусмотрены механизмы анализа и оптимизации построенных моделей ППР. Большинство инструментов хранит свои данные в текстовых файлах, что накладывает ограничения на размер онтологии.
Контрольный пример построения плана распределения ресурсов
Таким образом, в рамках данной работы получены следующие результаты: 1. Формализовано понятие процесса преобразования ресурсов, рассмотрены примеры III IP, выделены задачи предметной области ППР. При этом сформулированы критерии оптимизации в случае решения задач составления расписаний в условиях ограниченности ресурсов. 2. Показано, что рассматриваемые задачи ППР относятся к классу сложных систем, процесс проектирования которых связан с рядом трудностей: задачи оптимизации распределения ресурсов (средств) и проектирования новых ППР являются комбинаторными задачами большой размерности (с математической точки зрения задача является NP-полной); постоянно меняются условия функционирования ППР и приходится подстраиваться под них. 3. Определен перечень характеристик, которыми должна обладать система анализа и оптимизации ППР, и проведен сравнительный анализ распространенных ППП имитационного моделирования ППР и специализированных средств управления и планирования производственных процессов с целью анализа их возможностей для решения рассматриваемых задач. Определены достоинства и недостатки указанных систем. Отмечено, что, несмотря на давно возникший интерес к задачам ППР, до сих пор отсутствует единый инструмент решения задач анализа и синтеза ППР. Сформулированы требования к разрабатываемой программной системе. 4. Показана целесообразность разработки системы с использованием гетерархического мультиагентного подхода. 5. Проведена классификация процессов преобразования ресурсов. На основе данной классификации выделены основные элементы модели, образующие минимальный базис, необходимый для описания процессов ППР. Определены виды взаимодействий между ними. 6. Разработана математическая модель ППР на основе аппарата продукционных систем, учитывающая ограничения на ресурсы преобразования и целевые установки, как всего процесса, так и отдельных элементов. В рамках математической модели ППР определены: структура продукционной системы ППР, типы правил преобразования, графы смены состояний элементов модели, учитывающие возникновение конфликтов. 7. Показано, что разработанная математическая модель ППР является адекватным математическим описанием объекта моделирования, служит основой для построения алгоритмов и программ при машинной реализации модели. 8. На основе онтологического подхода разработана подсистема описания моделей процессов преобразования ресурсов, позволяющая концептуально моделировать ППР путем последовательного анализа и структурирования имеющихся данных об объекте моделирования. На основе предложенных во второй главе математических моделей элементов ППР разработан набор базовых мета-классов. 9. Применительно к модели ППР предложен алгоритм машины вывода, который учитывает специфику ППР и минимизирует вычисления. Определены пути ускорения работы машины вывода, обеспечивающие работу алгоритмов планирования и оптимизации расписаний в режиме реального времени. 10.Реализован алгоритм генерации имитационной модели из статической онтологической модели. 136 .Разработаны графическая нотация языка моделирования ППР, пользовательские интерфейсы, программное, информационное, методическое обеспечение, технология работы с системой. 12.Создан пакет прикладных программ анализа и оптимизации ППР, реализующий предложенный подход и позволяющий: создавать в диалоговом режиме онтологическую модель процесса ППР; проводить имитационные эксперименты с целью анализа характеристик процессов и выбора их эффективных реализаций; выполнять планирование и динамическую диспетчиризацию процессов преобразования ресурсов в соответствии с заданным критерием эффективности. Разработанная система анализа и оптимизации, обладает полным перечнем функциональных возможностей, предъявляемых к проблемно-ориентированному ППП и отличается: эффективными средствами моделирования конфликтов на общих ресурсах; понятийным аппаратом, ориентированным на проблемную область процессов преобразования ресурсов; стоимостью на порядок ниже аналогов. Теоретические результаты диссертации прошли проверку на тестовых экспериментах и подтвердили правильность и обоснованность разработанных положений и выводов.
