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

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ - УПИ

МОСКАЛЕВ ИЛЬЯ МИХАЙЛОВИЧ

СИСТЕМА АНАЛИЗА И ОПТИМИЗАЦИИ ПРОЦЕССОВ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

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

На правах рукописи

' /

Екатеринбург - 2006

Работа выполнена на кафедре «Автоматизированные системы управления» ГОУ ВПО «Уральский государственный технический университет - УПИ»

кандидат технических наук, доцент Клебанов Б.И.

доктор технических наук, доцент Суханов В.И.

кандидат технических наук, доцент Фирстов C.B.

Институт Машиноведения Уральского отделения Российской академии наук (г. Екатеринбург)

Защита состоится « tj » //¿'t/.p_ 2006 г. в !£> час 3Û мин. на заседании

диссертационного совета Д 212.285.11 при Уральском государственном техническом университете - УПИ (620002, г.Екатеринбург, К-2, Втузгородок, УГТУ-УПИ, 6-й учебный корпус, ауд. Р-217).

Отзыв на автореферат в одном экземпляре, заверенный гербовой печатью организации, просим направлять по адресу: 620002, г. Екатеринбург, ул. Мира, 19, ГОУ ВПО УГТУ-УПИ, ученому секретарю диссертационного совета Д 212.285.11 Важенину В.Г.

С диссертацией можно ознакомиться в библиотеке Уральского государственного технического университета - УПИ.

Автореферат разослан «. » ... ,/ги г 2006 г.

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

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

Ведущая организация:

Ученый секретарь диссертационного совета,

к.т.н., доцент f/[ В'Г"Важенин

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

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

Указанные задачи оптимизации распределения ресурсов (средств) и проектирования новых ППР относятся к классу сложных I систем - являются комбинаторными задачами большой размерности (с математической точки зрения задача является NP-полной). Для их решения применяются различного рода эвристики. Значительный интерес для решения данных задач представляет исследование возможности применения мультиагентного подхода к моделированию поведения автономных объектов с целью разделения общей задачи оптимизации на ряд частных подзадач, решаемых в рамках отдельных агентов, и получения согласованных и эффективных планов совместной работы агентов за ограниченное время.

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

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

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

Исходя из цели исследования, определены основные задачи:

1. Выполнить сравнительный анализ универсальных пакетов имитационного моделирования ППР и специализированных средств управления и планирования производственных процессов, установить их достоинства и недостатки для моделирования дискретных ППР.

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

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

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

5. Разработать ¡инструментальное программное средство для поддержки онтологического описания моделей, проведения имитационных экспериментов, анализа результатов и оптимизации ППР. \ ■

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

Научная новизна решения поставленных задач заключается в следующем:

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

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

3. Разработаны нотация и метаязык описания моделей процессов преобразования ресурсов.

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

I

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

На защиту выносятся следующие результаты исследований:

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

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

3. Алгоритмы мультиагентного моделирования процессов распределения ресурсов (алгоритм генерации мультиагентной имитационной модели на основе статической онтологической модели процесса, алгоритмы поведения активных' элементов).

Реализация результатов работы. Разработанное в диссертации программное обеспечение используется в учебном процессе Радиотехнического института Уральского государственного технического университета - УПИ. Результаты работы использованы компанией ЗАО «Микротест» при разработке технической концепции

построения корпоративной информационной системы ООО рКАМАЗавтотехник». Созданный инструмент онтологического моделирования апробирован на проектах, проводимых ЗАО «Институт программных систем». Внедрение экспериментальной версии системы анализа и оптимизации ППР . осуществлено в компании ЗАО «Уральский завод эластомерных уплотнений».

Реализация результатов работы подтверждается соответствующими актами.

I

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

• Международная научно-практическая конференция «СВЯЗЬ-ПРОМП 2006» в рамках III Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2006» (Екатеринбург, 2006); j

• Международная научно-практическая конференция «СВ^13Ь-ПРОМП 2005» в рамках II Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2005» (Екатеринбург, 2005); |

молодых

VII отчетной конференции (Екатеринбург, 2005); VI отчетной конференции (Екатеринбург, 2004); V отчетной конференции (Екатеринбург, 2003).

ученых ГОУ ВПО УГТУ-УПИ

молодых ученых ГОУ молодых ученых ГОУ

ВПО УГТУ-УПИ

ВПО УГТУ-УПИ

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

рекомендуемых ВАК. I

|

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (117 наименований) и приложения. Объем основной части работы - 170 страницы, 66 рисунков, 19 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность выбранной темы диссертационной работы, рассмотрены вопросы научной новизны и практической значимости работы, изложены основные положения, диссертации.

выносимые на защиту, сделан краткий обзор по главам

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

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

В работе выделены и описаны следующие задачи проблемной области ППР:

• прогноз состояния ресурсов и средств;

• оценка временах и стоимостных характеристик процесса;

• выявление «узких мест»;

• оценка максимального производства ППР и определение потребности в материалах для выпуска определенного объема продукции;

• анализ влияния^ одних процессов на другие;

• проектирование новых и совершенствование существующих ППР;

• управление действующими ППР.

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

В связи с чем в рамках данной работы проведен обзор программных продуктов, позволяющих решать перечисленные задачи: распространенных универсальных пакетов имитационного моделирования (Arena, AnyLogic, ReThink) и специализированных средств управления производством и планирования производственных процессов (SAP АРО - Production Planning and Detailed Scheduling, Zenith SPPS, Lekin, ФОБОС, SyteLine APS). В ходе анализа были определены недостатки и достоинства указанных пакетов, показано, что, несмотря на давно возникший интерес к задачам ППР, до сих пор отсутствует недорогой общий инструмент для решения задач имитационного моделирования, анализа и оптимизации ППР.

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

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

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

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

Для решения поставленных задач вводится классификация элементов ППР с точки зрения функционального соответствия элементов описываемым понятиям и возможности влияния| составных элементов на ход процесса. Множество ППР

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

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

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

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

Модель пассивного преобразователя представлена следующей структурой:

РР =< name, X, Y, F, Rules, prior, I, state >, (1)

где name - идентификатор преобразователя; Л' = j,/ = 1, jV- множество ресурсных входов преобразователя; )' = (у, },/ = \,М— множество выходов преобразователя; F — функция преобразования, определяющая правило перехода входных ресурсов в выходные: j

где ах - норма потребления ресурса по х, входу, axhO,l = l,N \ норма производства ресурса по у, выходу, Ьу £0,/ = 1,М; Тп/яо6 - время преобразования;

Rules = {rules,}, i - К - набор правил, определяющих поведение: преобразователя; I — интерпретатор правил, реализующий процесс прямого вывода^ state- состояние, в котором находится преобразователь в данный момент времени (рисунок 1):

• ожидание входных ресурсов (waiting) - преобразователь «накапливает» входной ресурс для преобразования в выходной, I

• преобразование ресурсов (producing) — в текущий момент идет «производство» выходного продукта,

• блокирован (locked) — преобразователь создал выходной продукт, но он еще не передан потребителю.

1 ! Вход преобразователя имеет

следующую структуру:

л:, =<resSupplier^ >,

КГ ä ^,

0 S S F™

j

Рисунок 1 - Диаграмма перехода состояний пассивного преобразователя Выход преобразователя представлен следующим образом: | =< resyi, ^ (г), , Consumeгл >,

! г*" г 6 .

I 'л »

(2)

>

где гм - ресурс, потребляемый преобразователем по от, входу; у™™. максимальный объем ресурса,

допустимый по входу х,; Г"'(О - текущее количество ресурса;

SupplierXi = {supj},y = 1, AT - множество

поставщиков res, ресурса.

(3)

j о v;w(o s у™™ ,

где rcs^ - ресурс, производимый преобразователем по выходу >■,; J^™" - максимальный объем ресурса, допустимый по выходу у,; - текущее количество ресурса;

Consumeryi = {conSj},j = \,К- множество потребителей resy ресурса преобразователя.

В рамках математической модели ПП определены правила преобразования и граф смены состояний, учитывающие ограничения на входной и выходной потоки ресурсов (см. рисунок 1, номера правил соответствуют номерам дуг): state'''' = waiting

1.

3.

4.

5.

, I = 1, N: У™' (/) <\aXi stateFr = waiting j Vre ,i = \j}:V"'(t)k

state'''' = locked t —T + AT

'mnt *иач.пр*о6. nptoß

3res. J = Ui:Vym(t) + 2-A >К™

> state = waiting

> state" = producing,Tm^ =tm„yres,, = (/)-*,■

>jta«"' = locked,Vres J = \,M:V""(t) = +

state

' - locked

3res

stale1''' = locked 3res , i = ¡TiV: VT"{t) < a Vre j., J = Ü7: FT (0 + k s v;

> state = locked ■

=> state = waiting >

6.

7.

^тек "^наы.преоб. ^^преоб

3res,,i = l,N:V™(t)<aXi => state™ = waiting,

\/reSy)j = им-.< f™

, i = 1, JV: K™'(0 in, => ¿/afe"" = producing, Tm4mt = <„„, Vre,^

sta/e^ = locked

= => state" = producing,TmJVm6 =t^,Vres,t =

= + SF™ j

Объем входного потока ресурсов определяется в соответствии с правилом:

' / ' => Г"г(0 = К"С) + С' (О = К71 (О-А^.

13supt: F^f' (/) > 0 * w * w * • * i

где AF, - количество «захватываемого» ресурса.

_ | с:; со. С* (о < К" - Т<'> ,

Объем выходного потока ресурсов определяется следующим правилом:

[bco^-V^U^V— => = V»r(,)" Т* = W + где AVyi - количество «отгружаемого» ресурса.

{ymnams, J/ma»cons, _ (/com,, < [

*' ' *' Л (5)

- к;;"1* (O >

Модель активного преобразователя представлена структурой:

ЛР=< name, X, Y, Z, F, Rules, Q,l>. (6)

где Y = y(,li{yl},i = l,M- множество выходов преобразователя,!^- основной выход

преобразователя; Z = {г, j^i = 1,1— множество необходимых для преобразования средств;

ß = {or<fer, },» = 1,п - перечень заявок, обслуживаемых преобразователем, I -

интерпретатор правил, реализующий процесс обратного планирования).

Структура средства представлена следующим образом:

г, =<mech^, Supplier. >, (7)

где mech, - идентификатор типа средств; Supplierz = {sup,},/ = 1, ЛГ - множество поставщиков mech, средства.

Структура заявки имеет следующий вид: .

order =<resn,V°"tr,Ttim,AC""r, slate,V,Jt),Vvm(i),(/)},{(ЛСр ,0.(0,'2.)} >. (8) где res — идентификатор ресурса, на который создана заявка; 7""1" - заказываемый объем ресурса; t,bm, - срок, к которому заявка должна быть выполнена; АС™"" - ссылка

вывода (обратного

на активный элемент, от которого поступила заявка; state - состояние, в котором находится заявка; Vtat() - объем продукта, зарезервированный под данную заявку на внутреннем складе продукта преобразователя; VnplJul(t) - объем продукта, находящийся в производстве; V"'p' (t) 'j объем j'-ro ресурса, зарезервированный под данную заявку на внутреннем складе входных ресурсов; АС"' - ссылка на активный элемент, от которого ожидается поступление ресурсов; — ожидаемый объем поступления /-го ресурса

от поставщиков для исполнения данной заявки; t™mi - ожидаемое время поступления г-го ресурса.

При этом справедливо следующее условие:

v"" = кло+к^ло+гсг;,?«)..........С; с J), (9).

Процесс обслуживания заявки представлен следующим графом переходов (рисунок 2). I

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

планирования, позволяем

динамически реагировать на изменения в системе и учитывает текущее состояние системы.

Алгоритм обслуживания заявок следующий. При поступлении очередной заявки на выходной ресурс она переходит в состояние «резервирование ресурсов и средств». Резервируются интервалы времени (XmmttTmi„t),k^\,pyt преобразователя под выполнение заявки, здесь рл /Ьл- необходимое количество циклов преобразования для создания продукта; Тюш„1 — время, при наступлении которого выполнение ¿-ого цикла преобразования должно быть окончено; Г„от m — время начала

I ■

выполнения к-ого цикла преобразования. Данные интервалы выбираются исходя из следующего условия:

Рисунок 2 — Диаграмма переходов - состояний заявки

Г <...<Т

янач.оп| *" на

t

т

жрез.нач I * юра.конt

(10)

„) = 0

где г^^ - запрашиваемый по (¡+1)-ой заявке срок поставки продукта; (7^, , щоН1) - зарез грвированные интервалы времени в работе преобразователя. Формируются заявки на поставку необходимых ресурсов:

V»™, = = = (1,-,/?Л), (11)

ю

где М— количество входных ресурсов. |

Если сроки поставки ресурсов поставщиками соблюдены, то заявка переходит в состояние «ожидание ресурсов». Если время поставки по какому-то ресурсу нарушено, то происходит процесс согласования. Выполняются следующие правила:

state'*' = violation

Iv/vr;:^,

- (т'*Ц т"1' )п(Т'

' V прейл.постк ' пост t ' V ю

Г'

зарез.нач * зарез.к

,) = 0"

i

state = reservation

\ >

предл.пост^ /

= min (О,

stale'*1 = violation

413T'*,J

яред.постъ > ^своб.1

• е (Т1

'. предя.постt V* эар<

VI Г*

ОН Г М СвСЧ

' зарез.кон *

state■■ Т' =Г*

Ha4.oiit ся'Я) ноч

= reservation :г'н

т-Г

1 j Св1

Г = т

nocmk * на

state"

-1» А np*d nocmk ' л предл.яосщ

= violation

,Т' ) state'*'= reject ■

10Ч> iapei.KOHJ 'Vbvt

предложены более

— т'

Если по заявке предложены более ранние сроки поставки ресурсов и преобразователь в эти моменты свободен, то резервируемый прд выполнение заявки интервал времени увеличивается (рисунок 4 а). Если в данные моменты времени преобразователь зарезервирован под выполнение работ по ¡другим заявкам, то осуществляется попытка перенести выполнение заявки. Если есть свободный интервал в работе преобразователя, удовлетворяющий критериям составления расписания, то он резервируется и осуществляется перезаказ ресурсов, иначе формируется отказ от выполнения работ по заявке (рисунок 3 б, в). 1

Ресурс 3 Ресурс 2 Ресурс 1

Время зарезервированное под другии заявки °

Время планируемо^ под выполнение анализируемой заявки

tt а 13 С-> С,

Предлагаемое время поставки ресурса

Ресурс 3 о Ресурс 3 •

Ресурс 2 о Ресурс 2

Ресурс 1 s"' Ресурс 1 !

| | Tpei I 1 | Трез !!

г И 12 13 11 12 13

С-. I е.,

6) ' в) |

Рисунок 3 — Определение интервала времени выполнения работ по заявке: а) увеличение интервала времени, отводимого под выполнение заявки; б) перенос работ по заявке на более ранний срок; в) отказ от выполнения заявки

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

lF(tl)=<ACь'g,AC^к',Mes(tl)>y (12)

где г, е[/0,...,{„] - момент времени, соответствующий наступлению события «запрос ресурса»; АС1*' - ссылка на активный элемент поставщик ресурса; ЛС'™1 - ссылка на активный элемент потребитель ресурса; - сообщение.

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

Сообщению «запрос на поставку

Приомни«

Источник

о_

сг

ресурса» структура:

Mes",

соответствует следующая

=<res,V'",t„

(13)

Г

Г

Рисунок 4 - Протокол обмена сообщениями

где V' — заказываемый объем ресурса;

срок, к которому ресурс должен быть поставлен.

Сообщению «ответ на запрос о поставке ресурса» соответствует следующая структура:

MesZ =< status, t„ocm, cos/ >, (1'4) где status - определяет, будет ли запрос выполнен в указанный срок или предлагается иной срок, или отказ от выполнения; tnocm, — предлагаемый со стороны поставщика момент времени поставки ресурса; cost - стоимость поставки указанного объема ресурса.

В рамках активных ППР предложен следующий набор критериев оценки качества планов ППР: !

1. Минимизация средневзвешенного момента окончания выполнения всех заявок

или максимального окончания соответственно:

I £v,C,->min, (15)

ы

тах(С, ) —► min. (16)

2. Минимизация j максимального временного смещения от заданного срока выполнения заявок, максимальной задержки, средневзвешенного временного смещения, средневзвешенной задержки выполнения соответственно:

I

j max(L,) -> min, (17)

max(7) )—»min. (18)

2>л

• mm.

(19)

w(7] —> min . (20)

3. Минимизация числа опоздавших заявок:

¿v,í/,-> min. (21)

i=i

4. Минимизация затрат, связанных с ожиданием наступления моментов начала выполнения заявок:

т Л

ZOEX +Z wt ■ -* min . (22)

где m - множество заявок; C¡ - момент выполнения заявки /, т.е. момент завершения ее последней операции j Oj. ; 0£,1>е\ = \,х, - множество операций, выполняемых над í-й заявкой; F, - длительность прохождения (производственный цикл) í-й заявки; L, -временное смещение заказа í; Ut - число опоздавших работ; v, - весовой коэффициент, учитывающий степень важности /-й заявки; Сц — себестоимость выполнения операции; w¡¡ - интервал времени между окончанием (®,-1)-й и началом т,-й операции í-й заявки; gf¡ - стоимость хранения ресурсов.

При планировании на хранилища ресурсов, внутренние входные и выходные буфера преобразователей наложены следующие ограничения:

= (23)

'«I

(24)

/-i

где V°'T' - объем у'-го входного ресурса, зарезервированного под í-ю заявку; F,""""' -объем поставки ./-го; ресурса по í-й заявке;^1"" - максимально допустимый объем хранилищау'-го ресурса; V""4 - объем продукта зарезервированного под í-ю заявку; К0™" - объем выходного хранилища.

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

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

Приоритет выполнения поступающих заявок определяется на основе следующих правил:

• первым пришел - первым обслужен (FIFO) - применяется, если при планирований заявки упорядочиваются в соответствии с их поступлением: min(r(,í = 1,л),

• ближайший срок готовности (EDD) - применяется, если при планировании максимальный приоритет имеет заявка с ближайшим сроком готовности: min(<i,,f = 1,и);

• максимальная длительность обработки (LPT) - применяется, если в первую очередь планируются заявки, имеющие самый длительный цикл обработки:

тах(р„,/ = 1,еу);

• минимальная длительность обработки (SPT) - применяется, если в первую очередь планируются заявки, имеющие самый короткий цикл обработки:

nrni0>u.» = l»8/).'

Здесь гj — момент поступления i-ro заказа в систему; с/, - плановый срок, к которому i'-й заказ должен быть выполнен; ри - время выполнения i-ro заказа.

На уровне отдельного преобразователя применение данных правил диспетчеризации позволяет оптимизировать определенные целевые функции. В таблице 1 перечислены данные правила, их вариации и указаны оптимизируемые целевые функции.

Таблица ! — Правила диспетчеризации

При вило ' ■ if и ! Целевая функция

1 SPT Заявки с меньшим временем выполнения обрабатываются первыми Тр,

2 LPT Заявки с большим временем выполнения обрабатываются первыми

3 WSPT Заявки упорядочиваются в порядке неубывания отношения времени их обработки к весовому коэффициенту f Д. VV

5 FIFO Заявки, поступившие в систему первыми, обслуживаются первыми п ^"max

6 EDD Заявки с наиболее ранними плановыми сроками обрабатываются первыми U ^max

7 TIS Заявки упорядочиваются в соответствии с временем их пребывания в системе ¿(Г-г.) с max

8 SLACK Заявки упорядочиваются, основываясь на временном резерве Т id, -1) ^max

Назначение средства из парка средств для выполнения О^ операции /-го заказа осуществляется исходя из следующего набора критериев:

• равномерная загрузка средств:

т!п(Л%11 ^ £ Р.А + Рма "ЕЕ Ли I). ' (25)

¿/.¡>»«(4) , } , ) |

где - длительность выполнения у-ой операции г'-го заказа на средстве .

• максимизация загрузки средств: '

(26)

где Тт - плановый период. '

При построении планов распределения ресурсов возможно использование методов прямого и обратного планирование. Оба метода работают со спецификацией продукта (рисунок 5).

I-1 . 2 . Р

ГЛг

¡Продукт

Сборка

У

О I 4 » б 7

Время

•) в) Рисунок 5 - а) спецификация продукта, б) временная структура продукта

При «планировании назад» построение расписания начинается с конечного продукта; точкой отсчета является дата, к которой продукт должен быть изготовлен. Далее последовательно определяются даты, к которым необходимо поставлять комплектующие. Если требуемые для обработки комплектующего средства заняты, то происходит перенос времени выполнения работы «назад», пока требуемый ресурс не окажется свободным.

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

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

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

В состав системы входят следующие подсистемы:

1. Подсистема сбора, хранения и предоставления информации по ПрО. С помощью данной подсистемы осуществляется описание объектов моделирования.

2. Подсистема проведения имитационных экспериментов и оптимизации ППР.

3. Подсистема формирования отчетов.

4. Подсистема предоставления \уеЬ-доступа к моделям.

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

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

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

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

1. Определение текущего момента времени — определяется модельного времени по системному календарю событий.

2. Определение списка активизированных объектов модели

ближайший момент

на момент времени

Рисунок б - Алгоритм функционирования машины вывода

3. Исполнение действий активизированными объектами модели и фиксация изменений в их рабочей памяти. Каждый получивший управление элемент модели:

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

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

• фиксация в глобальном календаре моментов времени очередной активизации элемента модели. !

Начало

Г

Выделение состава элементов ЬпР на основе онтологечжжой модели

Определение типа элемента модели

При этом происходит формирование заявок на поставку ресурсов, формирование заявок на поставку средств, согласование по заявкам, формирование ответов на заявки, производство продукта, поставка ресурса.

4. Расчет глобальных показателей и переменных.

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

Для повышения

производительности перед началом имитационного эксперимента

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

Алгоритм формирования приведен на рисунке 7. 1

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

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

Выделение перечня реквизитов злемента

формирование информационных ограничений на отношения между объектами

Формирование правил

раздета знвмений _рекя>иитов

объекты модели4 означены

Рисунок 7 - Алгоритм формирования объектной модели

200

На рисунке 8 показаны графики зависимостей быстродействия алгоритмов от размерности решаемых задач: без предварительной компиляции модели (А1), с предварительной компиляцией модели (А2) и оптимизированного (АЗ), в котором исключены повторяющиеся события. Использование различных методов повышения

производительности ; работы машины вывода позволило в задаче анализа, рассмотренной в главе 4 диссертации, сократить время проведения машинного эксперимента в 22,6 раза.

15 60

Размерность задачи

-А1 - - - А2-АЗ

Рисунок 8 — Сравнение алгоритмов

В четвертой главе рассмотрены примеры задач анализа и оптимизации ППР, решаемые системой. В частности, рассмотрена контрольная тестовая задача планирования загрузки оборудования при выполнении заказов на производство продукции двух типов при ограниченном числе средств и временных ограничениях, задача составления месячного плана производства на изготовление изделия СБ.8000 «Штепсельный разъем». При рассмотрении последней задачи промоделированы ситуации выхода из строя оборудования и поступления новых заказов в ходе производства, при этом были соответствующим образом скорректированы производственные планы.

Разработанная библиотека методов планирования предоставляет пользователю возможность выбора из 32 комбинации правил при проведении экспериментов.

Графики производственных циклов выполнения заказов при составлении расписания для тестовой задачи с использованием различных методик (ПВМН - прямой вывод, минимальная длительность цикла производства; ПВМК — прямой вывод, максимальная длительность цикла производства; ОВМК - обратный вывод, максимальная длительность цикла производства; ППВМН — прямой вывод, одновременное планирование всех заказов, минимальная длительность операции; ППВМК — прямой вывод, одновременное планирование всех заказов, максимальная длительность операции) приведены на рисунке 9. Из них видно, что в рассматриваемой задаче наименьший производственный цикл получается при составлении расписания методом прямого вывода при параллельном «проталкивании» всех операций работ и выборе операций с максимальной длительностью.

пвмс пвш сеж ППВЬК ] ПЛВ№<

Рисунок 9 - Производственный цикл выполнения заказов при различных методах планирования

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

—♦—пвмк -в—ПРМН овмк

-ж—теме - -*— ппкмн jBC,** •! в*

а) б)

Рисунок 10 — а) себестоимость производства продукции, б) затраты на хранение незавершенного

производства

В примере сборки изделия СБ.8000 «Штепсельный разъем» осуществлено составление расписания работ за период с 1 ноября по 1 декабря 2005 года. Изделие состоит из восьми деталей. Технологические маршруты деталей проходят через петь цехов, общее количество технологических операций 61. Наилучшее производственное расписание по критерию max(C,) -> min получено с использованием алгоритма прямого планирования, в первую

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

ш пи I» и an Mi an an an «и »л an Iii МИ an ли

Таким образом, проведенные вычислительные эксперименты подтвердили теоретические результаты работы и показали эффективность использования

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

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

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

1. Проведен сравнительный анализ наиболее распространенных пакетов имитационного моделирования - Arena, ReThink, AnyLogic и систем планирования и диспетчирования производства - ФОБОС, SAP АРО, Zenith SPPS, Lenkin с целью анализа их возможностей для решения рассматриваемых задач. Определены достоинства и недостатки указанных систем, сформулирован перечень характеристик, которыми должна обладать система анализа и оптимизации ППР. Показана целесообразность разработки системы с использованием гетерархического мультиагентного подхода.

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

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

4. Создана онтологическая система и метаязык описания | моделей процессов . преобразования ресурсов, позволяющие концептуально | моделировать ППР путём последовательного анализа и структурирования имеющихся данных об объекте моделирования. I

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

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

7. Создан пакет прикладных программ анализа и оптимизации ППР, реализующий предложенный подход и позволяющий: | ■

• создавать в диалоговом режиме онтологическую модель процесса ППР;

• проводить имитационные эксперименты с целью анализа характеристик процессов и выбора их эффективных реализаций;

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

Основное Содержание работы отражено в следующих публикациях:

1,- Москалев И.Mi Применение ГИС-технологий в имитационном моделировании пространственно-распределенных динамических процессов [Текст] / Б.И. Клебанов, H.Mi Москалев // Научные труды VI отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: Сборник статей. В 2 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ. - 2004. - 4 1. - С. 288-291.

2. Москалев И.М. Система учета и управления недвижимостью вуза «Карта УГТУ-УПИ» [Текст] /Б.И. Клебанов, И.М. Москалев // Вестник ГОУ ВПО УГТУ-УПИ. Проектирование и анализ радиотехнических и информационных систем / Серия радиотехническая. Екатеринбург: ГОУ ВПО УГТУ-УПИ. - 2004. - №18(48) -С. 189-197.

3.. Инструментарий создания КИС, основанный на имитационной модели предприятия [Электронный ресурс] / И.М. Москалев [и др.] // Девятая Всероссийская студенческая научно-техническая Интернет-конференция: Секция системотехника и информационные технологии. — 2004. - Режим доступа: http://webconf.rtf.ustu.ru/mod/forum/discuss.php?d=161.

4. Подходы в имитационном моделировании. Реализация средства построения имитационной модели предприятия [Электронный ресурс] / И.М. Москалев [и др.] // Девятая Всероссийская студенческая научно-техническая Интернет-конференция: Секция системотехника и информационные технологии. - 2004. -Режим доступа: http://webconf.rtf.ustu.ru/mod/forum/discuss.php?d=162.

5. Москалев, И.М. Применение имитационного моделирования для автоматизации проектирования комплексных информационных систем [Текст] / Б.И. Клебанов, И.М. Москалев // Вестник ГОУ ВПО УГТУ-УПИ. 50-летие радиотехнического образования на Урале. Серия радиотехническая. Екатеринбург: ГОУ ВПО УГТУ-УПИ. - 2004. - №20(50) - С. 224-226.

6. Москалев И.М: Основные подходы к имитационному моделированию [Текст] / И.М. Москалев, P.A. Камалтдинов // Научные труды VII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: Сборник статей. В 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ. - 2005. - Ч 1. - С. 86-87.

7. Москалев И.М. Система сбалансированных показателей [Текст] / И.М. Москалев, A.B. Попов // Научные труды VII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УЙИ: Сборник статей. В 3 ч. Екатеринбург: ГОУ ВПО УГТУ-УПИ. -2005.-41.-С. 96-97.

8. Москалев И.М. Применение онтологий при проектировании информационной системы предприятия [Текст] / Б.И. Клебанов, И.М. Москалев, И.А. Богданович // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМП 2005» в рамках II Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2005». - Екатеринбург: ЗАО «Компания Реал-Медиа», 2005. -С. 188-192.

• 9. Москалев И.М.!Система построения онтологий [Текст] / Клебанов Б.И., Москалев И.М., A.A. Пальцева // Вестник ГОУ ВПО УГТУ-УПИ: Спецвыпуск. Екатеринбург: ГОУ ВПО УГТУ-УПИ. - 2005. - С. 94-99.

Ю.Москалев И.М. Инструментальное средство анализа и синтеза процессов преобразований ресурсов «Онтомоделер» [Текст] / Б.И. Клебанов, И.М.

Москалев, Е.А. Быков // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМП 2006» в рамках III Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2006». - Екатеринбург, 2006. -С. 236-238.

П.Москалев И.М. Модель активного преобразователя ресурсов [Текст] / Б.И. Клебанов, И.М. Москалев // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМП 2006» в рамках III Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2006». - Екатеринбург, 2006. — С. 67-69.

Москалев Илья Михайлович

Система анализа и оптимизации процессов преобразования ресурсов

Автореферат

Формат 60x84/16 Заказ № 552

Подписано в печать 25.05.2006

Уч. изд. л. 1.0 Тираж 100 экз.

Отпечатано в салоне оперативной полиграфии АСМ-Электроника 620029, Екатеринбург, ул. Красноармейская, 1а :

ВВЕДЕНИЕ.

ГЛАВА 1. ПРОБЛЕМЫ АНАЛИЗА И ОПТИМИЗАЦИИ ПРОЦЕССОВ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ.

1.1 Процессы преобразования ресурсов.

1.1.1 Понятие процесса преобразования ресурсов.

1.1.2 Примеры процессов преобразования ресурсов.

1.2 Основные задачи анализа и оптимизации дискретных ППР.

1.2.1 Задачи анализа.

1.2.2 Задачи синтеза и управления ППР.

1.3 Обзор существующих инструментов описания, анализа, оптимизации и управления ППР.

1.3.1 Универсальные средства имитационного моделирования.

1.3.2 Средства управления производством и оптимизации производственных npoifeccoe.

1.3.3 Мультиагентный подход к планированию распределения ресурсов и ^ средств.

1.4 Математические методы оптимизации распределения ресурсов

1.4.1 Точные математические методы.

1.4.2 Эвристические методы.

Ф 1.5 Проблема и ее решение.

Выводы.

ГЛАВА 2. СТРУКТУРА И МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ СИСТЕМЫ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ.

2.1 Классификация процессов преобразования ресурсов.

2.2 Математическая модель ППР.

2.3 Математические модели преобразователей ресурсов.

2.3.1 Пассивные преобразователи ресурсов.

2.3.2 Активные преобразователи ресурсов.

2.3.3 Модель парка средств.

2.3.4 Модель хранилища ресурса.

2.3.5 Поток ресурсов и средств.

2.3.6 Информационный поток.

2.4 Формализация критериев качества планирования.

2.5 Машина вывода.

Выводы.

ГЛАВА 3. ПРИНЦИПЫ ПОСТРОЕНИЯ ПАКЕТА МОДЕЛИРОВАНИЯ И УПРАВЛЕНИЯ ПРОЦЕССАМИ ПРЕОБРАЗОВАНИЯ РЕСУРСОВ.

3.1 Онтологический подход к моделированию ППР.

3.2 Функциональные возможности пакета.

3.3 Принципы построения системы сбора, хранения и предоставления информации.

3.3.1 Принципы работы с системой.

3.3.2 Внутренний математический аппарат подсистемы.

3.3.3 Информационное обеспечение.

3.4 Подсистема моделирования ППР.

3.4.1 Агентский подход к моделированию ППР.

3.4.2 Алгоритмическое обеспечение.

3.5 Технология работы с пакетом анализа и оптимизации ППР.

Выводы.

ГЛАВА 4. РЕШЕНИЕ ЗАДАЧ АНАЛИЗА И ПЛАНИРОВАНИЯ.

4.1 Задачи анализа.

4.2 Задачи планирования.

4.2.1 Контрольный пример построения плана распределения ресурсов.

4.2.2 Составление производственного плана для изделия СБ.8000.

Выводы.

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

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

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

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

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

Исходя из цели исследования, определены основные задачи:

1. Выполнить сравнительный анализ универсальных пакетов имитационного моделирования ППР и специализированных средств управления и планирования производственных процессов, установить их достоинства и недостатки для моделирования дискретных ППР.

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

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

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

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

Объект исследования. Процессы преобразования ресурсов (ППР), планирование распределения ресурсов.

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

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

Научная новизна решения поставленных задач заключается в следующем:

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

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

3. Разработаны нотация и метаязык описания моделей процессов преобразования ресурсов.

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

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

На защиту выносятся следующие результаты исследований:

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

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

3. Алгоритмы мультиагентного моделирования процессов распределения ресурсов (алгоритм генерации мультиагентной имитационной модели на основе статической онтологической модели процесса, алгоритмы поведения активных элементов).

Реализация результатов работы. Разработанное в диссертации программное обеспечение используется в учебном процессе Радиотехнического института Уральского государственного технического университета - УПИ. Результаты работы использованы компанией ЗАО «Микротест» при разработке технической концепции построения корпоративной информационной системы ООО «КАМАЗавтотехник». Созданный инструмент онтологического моделирования апробирован на проектах, проводимых ЗАО «Институт программных систем». Внедрение экспериментальной версии системы анализа и оптимизации ППР осуществлено в компании ЗАО «Уральский завод эластомерных уплотнений».

Личный вклад автора состоит:

• в исследовании существующих средств имитационного моделирования и алгоритмов оптимизации распределения ресурсов;

• в разработке моделей ППР, основанных на аппарате продукционных систем и мультиагентном подходе;

• в разработке библиотеки алгоритмов планирования распределения ресурсов в сети активных преобразователей;

• в использовании онтологического подхода для описания процессов распределения ресурсов;

• в разработке программного пакета анализа и оптимизации ППР, его информационного, алгоритмического, методического и лингвистического обеспечения.

Апробация работы. Основные положения и результаты исследований диссертации докладывались автором на следующих международных, всероссийских, отраслевых и региональных конференциях и семинарах: Международная научно-практическая конференция «СВЯЗЬ-ПРОМП 2006» в рамках III Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2006»; Международная научно-практическая конференция «СВЯЗЬ-ПРОМП 2005» в рамках II Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2005»; VII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ; VI отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ.

Публикации. По теме диссертации опубликовано 11 научных работ, в том числе 9 печатных трудов в тематических сборниках и трудах научно-технических конференций российского и международного значения, из них 3 работы в рецензируемых изданиях, рекомендуемых ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (117 наименований), двух приложений. Объем основной части работы - 170 страниц, 66 рисунков, 19 таблиц.

Выводы

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

2. Система анализа и оптимизации ресурсов работоспособна и обеспечивает возможность:

• создания имитационных моделей дискретных процессов преобразования ресурсов;

• проведения структурного и параметрического синтеза модели процесса преобразования ресурсов;

• планирование распределения ресурсов;

• формирования отчетов по структуре процесса;

• формирования отчетов по результатам экспериментов;

• экспорта результатов экспериментов во внешние средства анализа данных;

• оценки состояния ресурсов и средств, временные и стоимостные характеристики процесса преобразования ресурсов;

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

ЗАКЛЮЧЕНИЕ

Таким образом, в рамках данной работы получены следующие результаты:

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

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

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

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

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

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

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

3 обеспечивающие работу алгоритмов планирования и оптимизации расписаний в режиме реального времени.

10.Реализован алгоритм генерации имитационной модели из ^ статической онтологической модели.

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

12.Создан пакет прикладных программ анализа и оптимизации ППР, реализующий предложенный подход и позволяющий:

• создавать в диалоговом режиме онтологическую модель процесса ППР;

• проводить имитационные эксперименты с целью анализа характеристик процессов и выбора их эффективных реализаций;

• выполнять планирование и динамическую диспетчиризацию процессов преобразования ресурсов в соответствии с заданным критерием эффективности.

Разработанная система анализа и оптимизации, обладает полным перечнем функциональных возможностей, предъявляемых к проблемно-ориентированному ППП и отличается:

• эффективными средствами моделирования конфликтов на общих ресурсах;

• понятийным аппаратом, ориентированным на проблемную область процессов преобразования ресурсов;

• стоимостью на порядок ниже аналогов.

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

1. Технология системного моделирования Текст. / Е.Ф. Аврамчук [и др.]; под общ. ред. А.А. Вавилова. М.: Машиностроение; Берлин: Техник, 1988.-520с.

2. Аксенов К.А. Исследование и разработка средств имитационного моделирования дискретных процессов преобразования ресурсов Текст.: дис. канд. техн. наук: 05.13.18 / К.А. Аксенов. Екатеринбург, 2003. -188 с.

3. Борщев А.В. Практическое агентное моделирование и его место в арсенале аналитика Текст. / А.В. Борщев // Exponenta Pro. Математика в приложениях. 2004. - №8.

4. Будник P. MES-системы: задачи и решения Текст. Тематический цикл. Часть 1 / Р. Будник // ЗАО "РТСофт", МКА. 2003. - №4

5. Будник Р. MES-системы в дискретном производстве Текст. / Р. Будник, В. Куминов // PC Week RE. 2003. - №46

6. Бусленко Н.П. Моделирование сложных систем Текст. / Н.П. Бусленко. М.: Наука, 1978.- 400с.

7. Вардан Г. Эволюция цепочек поставок Текст. / Г. Вардан //.PC Week RE. 2005. - № (489) 27. - С. 24

8. Вавилов А.А. Имитационное моделирование производственных систем Текст. / А.А. Вавилов. М.: Машиностроение; Берлин: Техник, 1983. -416с.

9. Витих В.А. Концепция управления открытыми организационными системами Текст. / В.А. Витих // Институт проблем управления сложными системами РАН, Самара, 1999.

10. Емельянов А.А. Имитационное моделирование экономических процессов Текст.: учеб. пособие / А.А. Емельянов, Е.А. Власова, Р.В. Дума; под ред. А.А. Емельянова. М.: Финансы и статистика, 2002. -368 с.

11. Гаврилов Д.А. Управление производством на базе стандарта MRP II Текст. / Д.А. Гаврилов 2-е изд. - СПб.: Питер, 2005. - 416 с.

12. Фролов Е.Б. "Ларчик" национальных технологических традиций открывает MES- система Текст. / И. Гладкова, Е.Б. Фролов // Оборудование. 2003. - №4 (76).

13. Горнев В.Ф. Оперативное управление в ГПС Текст. / В.Ф. Горнев, В.В. Емельянов, Овсянников М.В. — М.: Машиностроение, 1990. 256 с.

14. Горшков А.Ф. Компьютерное моделирование менеджмента Текст.: учеб. пособие / А.Ф. Горшков [и др.]; под общ. ред. Н.П. Тихомирова. М.: Экзамен, 2004. - 528 с.

15. Джексон П. Введение в экспертные системы Текст.: учеб. пособие / П. Джексон / Пер. с англ. М.: Издательский дом «Вильяме», 2001. - 624с.

16. Евгенев Г.Б. Мультиагентные системы компьютерной инженерной деятельности Текст. / Г.Б. Евгенев // Информационные технологии. -2000. № 4. - С.2-7.

17. Загидуллин P.P. Имитационные модели формирования расписаний в гибких производственных системах Текст. / P.P. Загидуллин // Технология машиностроения. 2004. - №3 - С.52-55.

18. Москалев И.М. Применение имитационного моделирования для автоматизации проектирования комплексных информационных систем Текст. / Б.И. Клебанов, И.М. Москалев // Вестник ГОУ ВПО УГТУ

19. УПИ. 50-летие радиотехнического образования на Урале / Серия радиотехническая. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2004. -№20(50) - С. 224-226.

20. Москалев И.М. Система построения онтологий Текст. / Б.И. Клебанов, И.М. Москалев, А.А. Пальцева // Вестник ГОУ ВПО УГТУ-УПИ: Спецвыпуск. Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. - С.94-99.

21. Кобелев Н.Б. Основы имитационного моделирования сложных экономических систем Текст.: учеб. пособие / Н.Б. Кобелев. М.: Дело, 2003. - 336 с.

22. Конвейн Р.В. Теория расписаний Текст. / Р.В. Конвейн, B.JI. Максвелл, JI.B. Миллер.: под ред. Г.П. Башарина; пер. с англ. М.: Наука, 1975. -360 с.

23. Курс ReThink Текст. Конспект лекций. АО «АРГУССОФТ КОМПАНИЯ». Москва, 1996.

24. Макаров И.М. Робототехника и гибкие автоматизированные производства Текст.: учеб. пособие: В 9 кн. Кн. 1: Системные принципы создания гибких автомтизированных производств / И.М. Макаров. М.: Высш. шк., 1986. - 174 с.

25. Маклаков С.В. Имитационное моделирование с Arena Текст. / С.В. Маклаков // Компьютер пресс. 2001. - №7. - С.135-136.

26. Марка Д. SADT Методология структурного анализа и проектирования Текст.: пер. с англ. / Д. Марка, К. МакГоуэн. - М., 1993. - 465с.

27. Мироносецкий Н.Б. Экономико-математические методы календарного планирования Текст. / Н.Б. Мироносецкий. Новосибирск: Наука, 1973. -140 с.

28. Москалев И.М. Система сбалансированных показателей Текст. / И.М. Москалев, А.В. Попов // Научные труды VII отчетной конференции молодых ученых ГОУ ВПО УГТУ-УПИ: Сборник статей. В 3 ч. -Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2005. Ч 1. - С. 96-97.

29. Питеркин С.В. Точно вовремя для России. Практика применения ERP-систем Текст. / С.В. Питеркин, Н.А. Оладов, Д.В. Исаев; под ред. И.Н. Букреева. М.: Альпина Паблишер, 2003 - 368с.

30. Питеркин С.В. КОГДА MRP НЕ РАБОТАЕТ. Текст. / С.В. Питеркин // Директор ИС. Издательство "Открытые системы". 2004. - №01.

31. Пищулов Г. Введение в теорию производства Текст.: учеб. пособие / Г. Пищулов, К. Рихтер, Е. Дятел. Екатеринбург: Изд-во Урал. гос. экон. ун-та, 2003.- 161с.

32. Попов С.М. Логистическое управление и составление расписаний в производственных системах Текст. / С.М. Попов, Е.И.Перовская // XXIX Неделя науки СПбГТУ. Материалы межвузовской научной конференции. СПб, 2001 - 4.VII - С. 79-80.

33. Статические и динамические экспертные системы Текст.: учеб. пособие / Э.В. Попов [и др.]; под общ. ред. Э.В. Попова М.: Финансы и статистика, 1996.-320 с.

34. Попов Э.В. Реинжиниринг систем управления предприятиями и современные информационные технологии Текст. / Э.В. Попов, Б.И. Клебанов НПП "ТЭКСИ", Екатеринбург, 1997. - 32с.

35. Искусственный интеллект Текст. — В 3-х кн. Кн. 2. Модели и методы: Справочник / под ред. Д.А. Поспелова М.: Радио и связь, 1990. - 304 с.

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

37. Риодан Дж. Введение в комбинаторный анализ Текст. / Дж. Риодан. М., 1963,-288 с.

38. Рубцов С.В. Интерпретация фактов в «интеллектуальной» системе имитационного моделирования Текст. / С.В. Рубцов, П.Г. Ивченко // Приборы и системы управления. 1992. - №4. - С. 3-4.

39. Саймон А.Р. Стратегические технологии баз данных: менеджмент на 2000 год Текст.: пер. с англ. / А.Р. Саймон; под ред. М.Р. Когаловского. -М.: Финансы и статистика, 1999.

40. Вениаминов Е. М. Система представления знаний Ontolingua принципы и перспективы Текст. / Е.М. Вениаминов, Д.М. Болдина // НТИ. - 1999. - сер. 2. - №10.

41. Смирнов С.В. Среда моделирования для построения инженерных теорий Текст. / С.В. Смирнов // Институт проблем управления сложными системами РАН. Самара, 1999.

42. Смирнов С.В. Онтологический анализ предметных областей моделирования Текст. / С.В. Смирнов // Институт проблем управления сложными системами РАН. Самара, 2001.

43. Советов Б.Я. Моделирование систем Текст.: учеб. для вузов / Б.Я. Советов, С. А. Яковлев-3-е изд., М.: Высш.шк., 2001.-343 с.

44. Сотсков Ю.И. Математические модели и методы календарного планирования Текст. / Ю.И. Сотсков, В.А. Струсевич, B.C. Танаев. -Минск: Университетское, 1994. 232 с.

45. Суханов В.И. Информационная технология принятия решений при открытой разработке месторождений Текст.: дис. д-ра техн. наук: 25.00.35 Екатеринбург, 2002. - 211с.

46. Тамм Б.Г. Анализ и моделирование производственных систем Текст.: пер. с англ. / Б.Г. Тамм, М.Э. Пуусепп, P.P. Таваст М.: Финансы и статистика, 1987.- 191 с.

47. Танаев B.C. Введение в теорию расписаний Текст. / B.C. Танаев, В.В. Шкурба. М.: Наука, 1975. - 428 с.

48. Филипс Д. Методы анализа сетей Текст.: пер. с англ. / Д. Филлипс, А. Гарсиа-Диас М.: Мир, 1984. - 496 е.: ил.

49. Форрестер, Дж. Основы кибернетики предприятия (Индустриальная динамика) Текст.: пер. с англ. / Под ред. Д.М. Гвишиани. М.: Прогресс, 1971.-340с.

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

51. Карпов Ю.Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5 Текст. / Ю.Г. Карпов. СПб.: БХВ-Петербург, 2005. - 400 с.

52. Рубцов С.В. Целевое управление корпорациями Электронный ресурс. — М., 2001. Режим доступа: http://or-rsv.narod.ru/Book/Book0.htm. - Дата доступа: 10.09.2003.

53. Танаев B.C. Теория расписаний Текст. / B.C. Танаев // Математика и кибернетика. 1988. - №2

54. Танаев B.C. Теория расписаний. Одностадийные системы Текст. / B.C. Танаев, B.C. Гордон, Я.М. Шафранский. М.: Наука, 1984. - 382 с.

55. Загидуллин P.P. Автоматизация производственных процессов в машиностроении Текст.: учеб. пособие / P.P. Загидуллин, К.С. Кульга; Уфим. гос. авиац. техн. ун-т. Уфа: УГАТУ, 1999. - 102 с.

56. Кале В. Внедрение SAP R/3. Руководство для менеджеров и инженеров Текст. / Вивек Кале. М.: Компания АйТи, 2004. - 470 с.

57. Кельтон Д.В. Имитационное моделирование Текст. / Д.В. Кельтон, A.M. Jloy 3-е изд. - СПб.: Питер; Киев: Издательская группа BHV, 2004. -847 с.

58. Модели распределения ресурсов и принятия решений в АСУ Текст.: сб. науч. тр. / МАИ; редкол.: М.Ф. Росин (пред.) [и др.]. М., 1982. - 85 с.

59. Гибкие системы управления: системные и математические модели Текст.: сб. науч. тр. / ВНИИМИУС; редкол.: Е.Т. Удовиченко (гл. ред.) [и др.]. Львов, 1985. - 96 с.

60. Экстремальные задачи оптимального планирования и проектирования Текст.: сб. науч. тр. / НАН Беларуси; науч. ред.: B.C. Танаев. Минск, 1991.-151 с.

61. Ершов А.Г. Теория программирования и вычислительные системы Текст. / А.Г. Ершов. М.: Знание, 1972.

62. Arena улучшает возможности для бизнеса в условиях новой экономики Электронный ресурс. Режим доступа: http://www.interface.ru/ sysmod/sysmodh.htm. - Дата доступа: 11.09.2003.

63. Baker A.D. A Survey of Factory Control Algorithms which Can be Implemented in a Multi-Agent Heterarchy: Dispatching, Scheduling, and Pull Text. / A.D. Baker // Manufacturing Systems. 1998.

64. Berker I. Conflicts and Negotiations in Single Function Agent Based Design Systems Text. / I. Berker, D. C. Brown // Concurrent Engineering Research and Applications. 1996. - Vol. 1. - № 1. - P. 17-35.

65. Van Brussel H. Holonic manufacturing control at K.U.Leuven Text. / H. Van Brussel, P. Valckernaers, L. Bongaerts, J. Wyns, P. Peeters // In: Proc. 9th IFAC Symp. on Information Control in Manufacturing (INCOM'98). 1998. -Vol. l.-P. 143-148.

66. Burke P. The Distributed Asynchronous Scheduler in Intelligent Scheduling Text. / P. Burke, P. Prosser // Eds. San Francisco, CA: Morgan Kaufmann. 1994.-P.-309-339.

67. Ham I. An integrated approach to group technology part family Db-design based on artificial intelligence techniques Text. / I. Ham, E. Goncales, C. Han // Annals of the CIRP. 1988. - №1. - P.37.

68. Garey M.R. Complexity of Flow Shop and Job Shop Scheduling Text. / M.R. Garey, D.S. Johnson, R. Sethi // Mathematics of Operations Research. 1976 -Vol.1 - №2. - P. 117-129.

69. Gonzalez T. Flowshop and Jobshop Schedules: Complexity and Approximation Text. / T. Gonzalez, S. Sahni // Operations Research. 1976 -Vol. 26.-№1.-P. 36-52.

70. Guarino N. Formal ontology, conceptual analysis and knowledge representation Text. / N. Guarino // Int. J. of Human Computer Studies. -1995. -Vol. 43. -№5/6.

71. Van Heijst G. Using explicit ontologies in KBS development Text. / Van G. Heijst, A. Th. Schreiber, B.J. Wielinga // Int. J. of Human Computer Studies. -1997.-Vol. 46.-№2/3.

72. Kaskavelis C. A. Integration of the Production Planning and Control Decision Process in a Manufacturing Enterprise Text. / C. A. Kaskavelis, M. C.

73. Caramanis // Working Paper, Department of Manufacturing Engineering, Boston University Technical Report, Boston, MA. 1995.

74. Lenstra J.K. Complexity of Scheduling Under Precedence Constraints Text. / J.K. Lenstra and A.H.G.R. Kan // Operations Research. 1978. - Vol. 26. -№2. - P. 22-35.

75. Maley J. G. Managing the Flow of Intelligent Parts Text. / J. G. Maley // In International Conference on the Manufacturing Science and Technology of the Future Cambridge, MA. June 3-7 1987.

76. Meyer M. Issues in Concurrent Knowledge Engineering: Knowledge Sharing and Knowledge Base Evolution Text. / Meyer M. // Concurrent Engineering: Research and Application. Proc. conf. CE94, USA. 1994.

77. Moulin B. An Overview of Distributed Artificial Intelligence Text. / B. Moulin, B. Chaib-Draa // In: Foundation of Distributed Artificial Intelligence (Eds. O'Hare, G.M.P and Jennings, N.R.), Chapter 1, John Wiley & Sons Inc., New York. 1996.

78. Newell A. Production systems: models of control structures Text. / A. Newell //Visual information processing. New York: Academic Press. -1973.-P. 463-526.

79. Michael D. Ontology Building: A Survey of Editing Tools Electronic resource./ Michael Denny O'Reilly's XML.com. Mode of access:http://www.xml.eom/pub/a/2004/07/14/onto.html, Date of access: 04.10.2004.

80. Parunak H.V.D. An Architecture for Heuristic Factory Control Text. / H. V. D. Parunak, J. F. White, P. W. Lozo, et al., // In Proceedings of the 1986 American Control Conference, Seattle, WA. June 18-20 1986. - P. 548-558.

81. Parunak H.V.D. Manufacturing Experience with the Contract Net, in Distributed Artificial Intelligence Text. / H. V. D. Parunak // Ed. Los Altos, CA: Morgan Kaufmann Publishers, Inc. 1987. - P. 285-310.

82. Parunak H.V.D. The Agent Architecture: An Example of Requirements-Driven Agent-Based System Design Text. / H.V.D. Parunak, A.D. Baker, S.J. Clark // Proceedings of the First International Conference on Autonomous Agents (Agents'97). 1997. - P. 482-483.

83. ReThink Release Notes Version 3.0 May 1997.

84. Shen W. An Agent-Based Approach for Dynamic Manufacturing Scheduling Text. / W. Shen, D.H. Norrie // In Working Notes of the Agent-Based Manufacturing Workshop, Minneapolis, MN. 1998. - P. 117-128.

85. Weisser P.Jr. Modeling Temporal Relations in Task Hierarchies for Job Shop Scheduling Text. / P.Jr. Weisser, S. Cochran // In Proceedings of the Second International Conference on Computer Integrated Manufacturing, Troy, NY, 1990, P. 39-46.

86. Wilson I. Synchronised manufacturing the route to zero inventory and maximum profitability Text. /1. Wilson //Logistics in Manufacturing. An IFS Executive Briefing. - 1983. - P. 111-117.

87. Wright A.B., Basic Scheduling Techniques Text. / A.B. Wright // In American Production & Inventory Control Society 1983 Conference• Proceedings.- 1983. P. 200-204.

88. APICS Dictionary, 10 ed. American Production and Inventory Control Society, 2002.

89. Ф 104. Schwiegelshohn U. Scheduling Problems and Solutions Electronic resource. /

90. Saad A. Performance Evaluation of Contract Net-Based Heterarchical Scheduling for Flexible Manufacturing Systems Text. / A. Saad, K.

91. Kawamura, G. Biswas // In American Production & Inventory Control Society1983 Conference Proceedings. 1983. - P. 200-204.

92. Sycara K. Distributed Constrained Heuristic Search Text. / K. Sycara, S. Roth, N. Sadeh, M. Fox // IEEE Transactions on Systems, Man, and

93. Cybernetics. IEEE Society. November-December 1991. - P. 1446-1461.

94. Manne A.S. On the Job Shop Scheduling Problem Text. / A.S. Manne // Operations Research. - 1960. - 8. - №2.

95. Wisner J.D. How Does Your Shop Stack Up? Text. / J.D. Wisner // Mrdern Machine Shop. 1993.- Vol. 66. - №2. - P. 86-90.

96. Blackstone J.D. A State-of-the-art Survey of Dispatching Rules for Manufacturing Job Shop Operations Text. / J.D. Blackstone, D.T. Phillips, G.L. Hogg // International Journal of Production Research. 1982. - Vol• 20.-№1.-P. 27-45.

97. Panwalkar S.S. A Survey of Scheduling Rules / S.S. Panwalkar, Iskander I. // Operation Research. 1977. - Vol. 25. -№1. - P. 45-61.

98. Brooks G.H. An Algorithm for Finding Optimal or Near-Optimal Solutions to the Production Scheduling Problem / G.H. Brooks, G.R. White // J. Ind. Eng.- 1965.-№1.-P.16.

99. Rajendran C. A Comparative Study of Dispatching Rules in Dynamic Ф Flowshops and Jobshops / C. Rajendran, O. Holthaus // European Journal of

100. Operational Research. 1999. - Vol. 116.-№1.-P. 156-170.

101. Gilmer J.B. Recursive Simulation to Aid Models of Decisionmaking / J.B. Gilmer, F.J. Sullivan // Proceedings of the 2000 Winter Simulation

102. Conference. 2000. - P. 958-963.

103. ГОСТ 34.602-89. ИТ. EKCAC. Техническое задание на создание автоматизированной системы Электронный ресурс. Взамен ГОСТ24.201-85; введ. 1990-01-01.--Режим доступа: http://www.interface.ru/sysmod/sysmodh.htm. — Дата доступа: 11.03.2005.

104. ГОСТ 34.601-90. ИТ. ЕКСАС. Автоматизированные системы. Стадии ^ создания Электронный ресурс. Введ. 1992-01-01. - Режим доступа:http://www.interface.ru/ sysmod/sysmodh.htm. Дата доступа: 11.03.2005.