Модели и методы разработки мультиагентных систем в планировании и диспетчеризации производства тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Никитин Николай Сергеевич

• Никитин Николай Сергеевич
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Никитин Николай Сергеевич

ВВЕДЕНИЕ

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ И ИНСТРУМЕНТОВ ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА, МУЛЬТИАГЕНТНЫЙ ПОДХОД

1.1 Обзор методов планирования и диспетчеризации производства

1.2 История развития мультиагентных систем

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

1.4 Современное состояние изученности мультиагентного подхода для решения задач планирования производства

ГЛАВА 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.4.1 Проектирование агентной среды

2.4.1.1 Определение ролей и построение модели ролей

2.4.1.2 Определение протоколов и формирование модели взаимодействия

2.4.2 Экспертная модель на базе метода МАЗ-Сошшоп КАОБ

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

2.4.3.1 Архитектура агента заказа

2.4.3.2 Архитектура агента ресурса

2.4.3.3 Архитектура управляющего модуля: "Доска"

ГЛАВА 3. МОДЕЛИРОВАНИЕ ПРОИЗВОДСТВЕННОГО ПРОЦЕССА С ИСПОЛЬЗОВАНИЕМ МУЛЬТИАГЕНТНОЙ МОДЕЛИ НА ПРИМЕРЕ МЕХАНИЧЕСКИХ ЦЕХОВ

3.1 Описание моделируемой среды

3.2 Моделирование агентной среды

3.3 Концептуальная модель СППР

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

Приложение А. Алгоритм поиска расписания методом поиска в ширину и

описание основных сущностей, включая вспомогательные алгоритмы

Приложение Б. Некоторые результаты поиска маршрутов реализации заказа

методом поиска в ширину

Приложение В. Ключевые алгоритмы и модули MAP

Приложение Г. Жадный рандомизированный адаптивный алгоритм поиска

допустимых распределений операций на рабочих центрах

Приложение Д. Алгоритм работы агента заказа

Введение диссертации (часть автореферата) на тему «Модели и методы разработки мультиагентных систем в планировании и диспетчеризации производства»

ВВЕДЕНИЕ

Актуальность темы исследования. Изменяющаяся природа глобализационных процессов в контексте новых геоэкономических вызовов и стремительно растущий уровень цифровизации общества привели к существенному обострению конкуренции на товарных, финансовых, энергетических и других рынках, что побуждает менеджмент предприятий искать новые методы управления, которые бы позволили достичь им отвечающего современным реалиям уровня качества обслуживания клиентов. CRM (Customer Relationship Management) и ERP (Enterprise Resource Planning) системы сегодня применяются бизнесом повсеместно, однако самого факта использования таких систем становится недостаточно для получения конкурентных преимуществ. ERP системы позволяют хранить, систематизировать и анализировать огромные объемы информации, что помогает менеджменту предприятий принимать эффективные управленческие решения, а также своевременно корректировать стратегию развития компании, однако системы такого класса не имеют средств для своевременной идентификации ресурсных потребностей и возможностей предприятия, которые позволяли бы оперативно перестраивать работу внутренних подразделений под меняющиеся условия внешней среды. Развитие искусственного интеллекта как научной дисциплины открывает новые возможности для бизнеса, позволяющие повысить экономическую эффективность и обеспечить своевременность управленческих решений. Исследования в области применимости различного рода направлений искусственного интеллекта для решения бизнес -задач на сегодняшний день носят ключевой характер во многих исследовательских центрах и институтах. Одним из направлений таких исследований являются мультиагентные системы, позволяющие решать сложные экономические задачи и задачи управления.

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

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

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

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

мультиагентного подхода, в частности. Данным вопросам посвящены труды отечественных и зарубежных ученых, изучающих методы и алгоритмы мультиагентного моделирования, математико-экономические модели планирования производственных процессов, модели кооперации агентов. Большой вклад в эти исследования и разработки внесли такие ученые, как: Бахтизин А.Р., Варшавский В.И., Граничин О.Н., Девятков В. В., Зайцев И. Б., Ильин И. В., Луценко Е. В., Макаров В.Л., Симонова Е.В., Скобелев П.О., Тарасов В.Б. и другие. Среди зарубежных ученых можно назвать следующих: Corkill D.D., Joseph B., Lenat D.B., Lesser V.R., Shoham Y., Wooldridge M.J. и других. Общий вывод по анализу научных источников свидетельствует о достаточной степени проработанности вопросов, связанных со спецификой планирования производственных процессов и с моделированием социально-экономических процессов. Можно отметить, что, несмотря на значительный вклад исследователей в развитие мультиагентных технологий, их применение для оптимизации процессов производственных предприятий, в том числе в задачах планирования и диспетчеризации производства, требует дальнейшего изучения и развития. Исходя из вышесказанного была сформирована цель и задачи настоящего исследования.

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

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

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

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

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

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

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

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

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

Теоретической основой исследования является теория расписаний, исследования и разработки в области мультиагентных технологий, разработки в области эвристических и мета эвристических алгоритмов решения КР задач, а

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

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

Соответствие диссертации паспорту научной специальности.

Диссертационная работа выполнена в соответствии с пунктами: 4. «Разработка и развитие математических и компьютерных моделей и инструментов анализа и оптимизации процессов принятия решений в экономических системах.», 13. «Агентно-ориентированное моделирование сложных экономических систем» и 18. «Развитие и применение инструментария проектирования, разработки и сопровождения информационных систем в интересах субъектов экономической деятельности» паспорта специальности 5.2.2 - Математические, статистические и инструментальные методы экономики.

Научная новизна работы раскрывается в основных положениях, выносимых на защиту:

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

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

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

• Предложена концептуальная модель системы поддержки принятия решений (далее - СППР) на базе мультиагентной модели планирования производственных процессов, совершенствующая существующие подходы к разработке СППР для промышленных предприятий

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

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

Практическая значимость результатов диссертационной работы

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

допустимые решения задачи распределения операций по рабочим центрам (по

заданному критерию оптимизации), которые могут приближаться к оптимальному

9

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

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

Апробация и реализация результатов исследования. Результаты работы обсуждались на семинарах и конференциях:

• Международный онлайн-семинар «Искусственные общества и информационные технологии» ЦЭМИ РАН

• 33-я международная конференция IBIMA Education Excellence and Innovation Management through Vision 2020 (Гранада, 2019 г.).

• Семинары Высшей школы бизнес-инжиниринга

По теме диссертации опубликовано 8 печатных работ, в том числе 5 в изданиях, входящих в перечень ВАК. Материалы диссертационного исследования отображены достаточно полно.

Объем и структура работы. Диссертация состоит из введения, трех глав,

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

исследования, описаны пункты новизны, представлены цель и задачи

исследования. В первой главе рассмотрены существующие методы планирования

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

10

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

Объем диссертации составляет 202 страницы, включая 48 рисунков, 11 таблиц, а также 5 приложений. Список литературы содержит 123 наименования.

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДОВ И ИНСТРУМЕНТОВ ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА, МУЛЬТИАГЕНТНЫЙ ПОДХОД

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

1.1 Обзор методов планирования и диспетчеризации производства

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

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

определиться с тем, какая степень детализации плана интересует заказчика. По степени детализации можно выделить следующие виды планирования:

• Объемное — определяется производственная мощность всего предприятия, а также прорабатывается номенклатура и трудоемкость. Разрабатывается производственная программа и баланс ресурсов;

• Объемно-календарное — происходит согласование планов по объему выпуска и по времени исполнения, формируется производственная программа, которая привязывается к срокам запуска и выпуска;

• Оперативное — составляется детальный график производства и выпуска продукции с учетом находящихся в расположении ресурсов.

Производственные планы первых двух уровней применяются для разработки стратегии предприятия, а оперативный план необходим для обеспечения работы по координации и выполнению производственной программы. Несомненно, для того чтобы выполнять глобальные стратегические задачи, производственные процессы должны быть оптимизированы с точки зрения их слаженности, загрузки рабочих мощностей, соблюдения сроков выполнения заказов, минимизации переналадок и т. д. Правильный выбор метода планирования и диспетчирования позволяет оптимизировать оперативный план производства [2]. Остановимся подробнее на различных методах планирования, отранжируя их по времени появления. MRP - планирование потребностей в материалах.

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

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

2) Расчет нетто-потребностей во времени с учетом правил партии, минимального количества партии заказа, периодичности и прочих ограничений с учетом прихода и расхода материала для вычисления разницы

между плановым количеством материала и текущим.

13

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

Общая схема представлена на Рисунке 1.1.

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

Методика MRP II наиболее широко используется в современных системах планирования ресурсов предприятия. Алгоритм планирования выглядит следующим образом:

1. Определение потребности в готовой продукции с учетом параметров спроса. На основании объема заказа клиентов и прогноза уровня спроса формируется основной производственный план, алгоритм расчета которого зависит от типа производства: на склад, под заказ.

2. Определение брутто-потребностей в материалах и сборках на основании основного плана производства и спецификации изделия.

Для этого определяются нетто-потребности на производимые и

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

Методика MRP II используется в таких информационных системах планирования производства, как: Omega Production, SAP/R3, ERP-Галактика, Microsoft Dynamics AX, Фрегат Корпорация. Методика наследовала MRP, включив в себя ряд модулей для планирования ресурсов предприятия Алгоритм планирования по методологии MRP II представлен на Рисунке 1.2.

Рисунок 1.2 - Алгоритм планирования MRP II Согласно стандарту MRP II, соответствующие системы должны иметь следующие модули:

o Планирование развития бизнеса o Планирование деятельности предприятия; o Планирование продаж;

o Планирование потребностей в сырье и материалах (MRP); o Планирование производственных мощностей (CRP);

15

o Планирование закупок;

o Выполнение плана производственных мощностей; o Выполнение плана потребности в материалах.

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

• Запаздывающее реагирование на изменения из-за периодического (а не динамического) пересчёта планов.

• Высокая вычислительная сложность из-за итеративного подхода и необходимости согласования планов по материалам и мощностям.

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

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

APS - синхронное планирование производства.

Метод синхронного планирования производства можно разделить на две составные части: планирование производства со снабжением и диспетчеризация производства. Планирование производства и снабжения представляет собой процесс, основанный на методике MRP II, однако в рамках APS на первых стадиях планирования закупки или производства необходимых изделий учитываются ограничения производственных мощностей и их текущая загруженность производственными заданиями. Это позволяет сразу закладываться на текущие и общие ограничения, не порождая цепочку перепланирований из-за допущений, сделанных на предыдущем шаге. В этом заключается синхронность процесса планирования, делающая метод APS наиболее привлекательным с точки зрения скорости процедуры планирования.

Алгоритм планирования APS:

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

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

3. Итеративная оптимизация. На каждом шаге добавляются менее строгие ограничения (минимизация переналадок, простоев). Процесс повторяется до достижения баланса между всеми критериями. Результат — выполнимое расписание, близкое к оптимальному.

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

• Планирование с учетом ограничений и загруженности мощностей производства, что позволяет получать выполнимые планы с минимальными корректировками

• Возможность определить реальную дату выполнения заказа;

• Высокая скорость перепланирования графика производства, его корректировка с учетом отклонений в ходе производства или изменений в заказах;

• Максимальная загрузка ресурсов производства, снижение количества узких мест

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

Метод синхронного планирования используется в таких информационных системах планирования производства, как: Omega Production, Microsoft Dynamics AX, Preactor.

Недостатками метода APS являются:

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

Список литературы диссертационного исследования кандидат наук Никитин Николай Сергеевич, 2025 год

СПИСОК ЛИТЕРАТУРЫ

1. Heizer, J. Operations Management : Sustainability and Supply Chain Management / J. Heizer, B. Render, C. Munson. — 13th ed. — Harlow : Pearson, 2021. — 768 p.

2. Pinedo, M. L. Planning and Scheduling in Manufacturing and Services / M. L. Pinedo. - 2nd ed. - New York : Springer, 2012. - 536 p.

3. Orlicky, J. Material Requirements Planning: The New Way of Life in Production and Inventory Management / J. Orlicky. - New York : McGraw-Hill, 1975. - 352 p.

4. Zhang, L. Multi-Agent Based Production Planning and Control / L. Zhang, Y. Wang // International Journal of Production Research. - 2018. - Vol. 56, № 1-2. -P. 422-445.

5. Stadtler, H. Supply Chain Management and Advanced Planning / H. Stadtler, C. Kilger. - 6th ed. - Berlin : Springer, 2021. - 557 p.

6. Пригожин, И. Р. Порядок из хаоса : новый диалог человека с природой / И. Р. Пригожин, И. Стенгерс ; пер. с англ. .— М. : Едиториал УРСС, 2003 .— 312 с.

7. Хакен, Г. Информация и самоорганизация : макроскопический подход к сложным системам / Г. Хакен ; пер. с англ. .— М. : КомКнига, 2005 .— 248 с.

8. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning / D. E. Goldberg .— Reading, Mass. : Addison-Wesley, 1989 .— 412 p.

9. Ashby, W. R. An Introduction to Cybernetics / W. R. Ashby. - London : Chapman & Hall, 1956. - 295 p

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

11. Варшавский, В. И. Коллективное поведение автоматов / В. И. Варшавский .— М. : Наука, 1973 .— 408 с.

12.Wooldridge, M. An Introduction to Multiagent Systems / M. Wooldridge .— 2nd ed. .— Chichester : John Wiley & Sons, 2009.

13. Городецкий, В. И. Информационные технологии и многоагентные системы / В. И. Городецкий // Проблемы информатизации. — 1998. — Вып. 1. — С. 3-14.

14. Ларичев, О. И. Теория и методы принятия решений, а также Хроника событий в Волшебных Странах : учебник / О. И. Ларичев .— М. : Логос, 2000 .— 390 с.

15. Осипов, Г. С. Приобретение знаний интеллектуальными системами / Г. С. Осипов .— М. : Наука, 1997 .— 112 с.

16. Ларичев, О. И. Качественные методы принятия решений / О. И. Ларичев, Е. М. Мошкович .— М. : Физматлит, 1996 .— 207 с.

17.Трахтенгерц, Э. А. Компьютерная поддержка переговоров при выработке групповых решений / Э. А. Трахтенгерц .— М. : ИПУ РАН, 2001 .— 82 с.

18. Трахтенгерц, Э. А. Компьютерная поддержка переговоров при согласовании управленческих решений / Э. А. Трахтенгерц .— М. : Синтег, 2003 .— 284 с.

19. Швецов, А. Н. Распределенные интеллектуальные информационные системы / А. Н. Швецов, С. А. Яковлев .— СПб. : Изд-во СПбГЭТУ «ЛЭТИ», 2003 .— 318 с.

20.Арсеньев, Б. П. Интеграция распределенных баз данных / Б. П. Арсеньев, С. А. Яковлев .— СПб. : Лань, 2001 .— 464 с.

21.Demazeau, Y. Decentralized Artificial Intelligence / Y. Demazeau, J.-P. Muller (eds.) .— Amsterdam : Elsevier, 1990.

22.Пэранек, Г. В. Распределенный искусственный интеллект / Г. В. Пэранек // Искусственный интеллект : применение в интегрированных производственных системах / ред. Э. Кьюсиак .— М. : Машиностроение, 1985.

23.Rasmussen, J. Distributed Decision-Making : Cognitive Models for Cooperative Work / J. Rasmussen, B. Brehmer, J. Leplat (eds.) .— N. Y. : Wiley, 1991.

24.Wooldridge, M. Intelligent Agents : Theory and Practice / M. Wooldridge, N. R. Jennings // Knowledge Engineering Review. — 1995. — Vol. 10, № 2. — P. 115-152.

25.Ambros, J. Integrating planning, execution and monitoring / J. Ambros, S. W. D. Steel // Proc. of the 7th National Conference on Artificial Intelligence (AAAI-88). — St. Paul, MN, 1988. — P. 83-88.

26.Bratman, M. E. Plans and resource-bounded practical reasoning / M. E. Bratman, D. J. Israel, M. E. Pollack // Computational Intelligence. — 1988. — № 4. — P. 349-355.

27.Wood, S. Planning and Decision Making in Dynamic Domains / S. Wood .— Chichester : Ellis Horwood, 1993.

28. Vere, S. A basic agent / S. Vere, T. Bickmore // Computational Intelligence. — 1990. — № 6. — P. 41-60.

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

30.**An algorithm for machine search of natural logical deduction in prepositional calculus / N. A. Shanin, G. V. Davydov, S. Yu. Maslov [et al.] // Automation of Reasoning : Classical Papers. — 1983. — Vol. 1. — P. 25-47.

154

31. Gupta, A. Parallelism In Production Systems / A. Gupta .— Los Altos, CA : Morgan Kaufmann, 1987 .— 224 p.

32.Neiman, D. Design and Control of Parallel Rule Firing Production System : PhD Thesis / D. Neiman .— Amherst : University of Massachusetts, 1992.

33.**Programming Expert Systems in OPS5 : An Introduction to Rule-Based Programming / L. Brownston, R. Farrell, E. Kant, N. Martin .— Reading, Mass. : Addison-Wesley, 1985 .— 471 p.

34. Sherman, P. D. An OPS5 Primer : Introduction to Rule-Based Expert Systems / P. D. Sherman, J. C. Martin .— Englewood Cliffs, NJ : Prentice Hall, 1990 .— 193 p.

35. Ковригин, О. В. Гибридные средства представления знаний в системе СПЭИС / О. В. Ковригин, К. Г. Перфилев // Всесоюз. конф. по искусственному интеллекту : тез. докл. : в 2 т. — Переславль-Залесский, 1990. — Т. 2. — С. 56-61.

36. Попов, Э. В. Динамические интеллектуальные системы в управлении и моделировании / Э. В. Попов .— М. : МИФИ, 1996 .— 112 с.

37. Гильберт, Д. Основания математики : логические исчисления и формализация арифметики / Д. Гильберт, П. Бернайс .— М. : Наука, 1979 .— 560 с.

38.Клини, С. К. Математическая логика / С. К. Клини .— М. : Мир, 1973 .— 480 с.

39.Карри, Х. Б. Основания математической логики / Х. Б. Карри .— М. : Мир, 1969 .— 568 с.

40.Ершов, Ю. Л. Математическая логика / Ю. Л. Ершов, Е. А. Палютин .— М. : Наука, 1979 .— 320 с.

41.Малпас, Дж. Реляционный язык Пролог и его применение / Дж. Малпас ; пер. с англ. ; под ред. В. Н. Соболева .— М. : Наука, 1990 .— 464 с.

42.Clocksin, W. F. Programming in Prolog / W. F. Clocksin, C. S. Mellish .— Berlin : Springer, 1984 .— 324 p.

43. Kowalski, R. A. Logic for Problem Solving / R. A. Kowalski .— Amsterdam : North-Holland, 1979.

44. Robinson, J. A. A machine-oriented logic based on the resolution principle / J. A. Robinson // Journal of the ACM. — 1965. — Vol. 12, № 1. — P. 23-41.

45. Robinson, J. A. Logic : Form and Function / J. A. Robinson .— Edinburgh : Edinburgh University Press, 1979.

46.Цейтин, Г. С. Программирование на ассоциативных сетях / Г. С. Цейтин // ЭВМ в проектировании и производстве. — 1985. — Вып. 2. — С. 16-48.

47.Хейес-Рот, Ф. Построение экспертных систем / Ф. Хейес-Рот, Д. Уотерман, Д. Ленат .— М. : Мир, 1987 .— 430 с.

48. Minsky, M. A framework for representing knowledge / M. Minsky // The Psychology of Computer Vision. — N. Y. : McGraw-Hill, 1975. — P. 211-277.

49. Минский, М. Фреймы для представления знаний / М. Минский ; пер. с англ. .— М. : Мир, 1979 .— 152 с.

50.Шенк, Р. Познать механизмы мышления / Р. Шенк, Л. Хантер // Реальность и прогнозы искусственного интеллекта. — М. : Мир, 1987. — С. 49-56.

51.Байдун, В. В. Средства представления и обработки знаний в системе FRL/PS / В. В. Байдун, А. И. Бунин // Всесоюз. конф. по искусственному интеллекту : тез. докл. : в 2 т. — Минск, 1990. — Т. 1. — С. 66-71.

52. Стрельников, Ю. Н. Разработка экспертных систем средствами инструментальной оболочки в среде MS Windows / Ю. Н. Стрельников, Н.

A. Борисов .— Тверь : ТГТУ, 1997 .— 89 с.

53.Sisodia, R. AI in business and management / R. Sisodia, M. Warkentin // PC AI.

— 1992. — Jun/Feb. — P. 32-34.

54.Gruber, T. R. A translation approach to portable ontologies / T. R. Gruber // Knowledge Acquisition. — 1993. — Vol. 5, № 2. — P. 199-220.

55.Lenat, D. B. CYC : A Large-Scale Investment in Knowledge Infrastructure / D.

B. Lenat // Communications of the ACM. — 1995. — Vol. 38, № 11. — P. 3348.

56.Braetman, J. A. The Generalized Italian, German, English Upper Model / J. A. Braetman, D. Magnini, F. Rinaldi // ECAI'94. — Amsterdam, 1994.

51.TOVE Manual / Department of Industrial Engineering, University of Toronto.

— 1999. — URL: http://www.eil.utoronto.ca/tove/ontoTOC.html (дата обращения: 12.10.2023).

52. Van der Vet, P. E. The Plinius Ontology of Ceramic Materials / P. E. Van der Vet, N. J. Mars, P. H. Speel // ECAI'94. — Amsterdam, 1994.

53. Agent Builder: An Integrated Toolkit for Constructing Intelligent Software Agents / Reticular Systems, Inc. — 1999. — 210 p.

54.Shoham, Y. Agent-oriented programming / Y. Shoham // Artificial Intelligence.

— 1993. — Vol. 60, № 1. — P. 51-92.

55.Labrou, Y. A Proposal for a new KQML Specification / Y. Labrou, T. Finin. — 1997. — 45 p.

56.Searle, J. R. Foundations of Illocutionary Logic / J. R. Searle, J. B. Wanderveken. — Cambridge : Cambridge Univ. Press, 1985. — 227 p.

57.Human Agent Interaction // FIPA96 Draft Specification: Part 8. — URL: http://www.cset.it/fipa/fipa8713.doc (дата обращения: 12.10.2023).

58. Тарасов, В. Б. Предприятия XXI века: проблемы проектирования и управления / В. Б. Тарасов // Автоматизация проектирования. — 1998. — № 4. — С. 35-38.

59.Зильбершац, А. Стратегические направления в системах баз данных / А. Зильбершац, С. Здоник // Системы управления базами данных. — 1997. — № 4. — С. 20-25.

60.Hardwick, M. Sharing manufacturing information in virtual enterprises / M. Hardwick, D. Spooner, T. Rando, K. Morris // Communications of the ACM. — 1996. — Vol. 39, № 2. — P. 46-54.

61. Тарасов, В. Б. Виртуальное предприятие - ключевая стратегия автоматизации и перестройки деловых процессов / В. Б. Тарасов // Электронный офис. — 1996. — Октябрь. — С. 2-3.

62.Солдатов, А. В. Интеграция корпоративных информационных систем на базе XML / А. В. Солдатов // Автоматизация и управление в машиностроении. — 2001. — № 17. —

URL: http://magazine.stankin.ru/arch/n17/ (дата обращения: 12.10.2023).

63.Клементе, Т. Обзор SOAP / Т. Клементе. —

URL: http://www.javagu.ru/index.shtml?section=34&article=1381 (дата обращения: 12.10.2023).

64.Вютрих, Х. А. Виртуализация как возможный путь развития управления / Х. А. Вютрих, А. Ф. Филипп // Проблемы теории и практики управления. — 1999. — № 5. — С. 35-40.

65. Управление производством : учебник / под ред. Н. А. Саломатина. — М. : ИНФРА-М, 2001. — 219 с. — (Серия "Высшее образование").

66. Виноградов, А. Н. Разработка и исследование моделей и методов построения архитектуры и интеллектуальных средств для динамических интеллектуальных систем : дис. ... д-ра техн. наук : 05.13.18 / Александр Николаевич Виноградов. — М., 2002. — 310 с.

67. Скобелев, П. О. Разработка мультиагентной системы планирования, прогнозирования и моделирования производства / П. О. Скобелев // Мехатроника, автоматизация, управление. — 2001. — № 3. — С. 22-30.

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

69.Скобелев, П. О. Моделирование холонических систем / П. О. Скобелев // Труды II Международной конференции "Проблемы управления и моделирования в сложных системах". — Самара, 2000. — С. 45-52.

70. Виттих, В. А. Мультиагентные системы для моделирования процессов самоорганизации и кооперации / В. А. Виттих, П. О. Скобелев // Proc. of XIII International Conference on the Application of Artificial Intelligence. — 2001. — P. 112-120.

71. Трахтенгерц, Э. А. Неопределенность в моделях компьютерных систем поддержки принятия решений / Э. А. Трахтенгерц // Новости искусственного интеллекта. — 2001. — № 5-6. — С. 5-15.

72. Тарасов, В. Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и искусственном интеллекте / В. Б. Тарасов // Новости искусственного интеллекта. — 1999. — № 3. — С. 7-15.

73.Nwana, H. S. Software Agents: An Overview / H. S. Nwana // Knowledge Engineering Review. — 1996. — Vol. 11, № 3. — P. 1-40.

74.Sloman, A. What sort of architecture is required for a human-like agent? / A. Sloman // Proc. of Cognitive Modeling Workshop, AAAI-96. — Portland, 1996. — P. 34-41.

75. Хорошевский, В. Ф. PIES технология и инструментарий PIES Work Bench для разработки систем, основанных на знаниях / В. Ф. Хорошевский // Новости искусственного интеллекта. — 1995. — № 2. — С. 7-64.

76.Kornfeld, W. A. The Scientific Community Metaphor / W. A. Kornfeld, C. E. Hewitt // IEEE Transactions on Systems, Man, and Cybernetics. - 1981. - Vol. SMC-11, No. 1. - P. 24-33.

77.Lenat, D. B. BEINGS: Knowledge as Interaction / D. B. Lenat, C. Hewitt // Proceedings of the 5th International Joint Conference on Artificial Intelligence (IJCAI'77). - 1977. - P. 126-133

78. Smith, R. G. The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver / R. G. Smith // IEEE Transactions on Computers. - 1980. - Vol. C-29, No. 12. - P. 1104-1113

158

79. Lesser, V. R. The Distributed Vehicle Monitoring Testbed: A Tool for

Investigating Distributed Problem Solving Networks / V. R. Lesser, D. D. Corkill // AI Magazine. - 1983. - Vol. 4, No. 3. - P. 15-33

80.Shoham, Y. Agent-Oriented Programming / Y. Shoham // Artificial Intelligence. - 1993. - Vol. 60, No. 1. - P. 51-92

81. Старостин, Д. Готовность систем управления предприятием к интеграции / Д. Старостин // Byte Magazine Online. — 2002. —

URL: http://www.bytemag.ru/Article.asp?ID=426 (дата обращения: 12.10.2023).

82. Катаев, А. В. Виртуализация как возможный путь развития управления / А. В. Катаев. — URL: http: / /business .rin.ru/cgi-

bin/search.pl?action=view&num=341295&razdel=8 (дата обращения: 12.10.2023).

83. Швецов, А. Н. Интеллектуальные методы объектно-ориентированного проектирования сложных информационных систем / А. Н. Швецов // Информационные технологии в образовании, технике и медицине : сб. науч. тр. — 2002. — С. 45-52.

84. Суконщиков, А. А. Разработка математических методов проектирования информационных систем на основе информационно-вычислительных сетей / А. А. Суконщиков, А. Н. Швецов // Вестник ВоГТУ. — 2001. — № 2. — С. 67-72.

85. Ковригин, О. В. Гибридные средства представления знаний в системе СПЭИС / О. В. Ковригин, К. Г. Перфилев // Всесоюз. конф. по искусственному интеллекту : тез. докл. : в 2 т. — Переславль-Залесский, 1990. — Т. 2. — С. 56-61.

86. Хорошевский, В. Ф. Поведение интеллектуальных агентов: модели и методы реализации / В. Ф. Хорошевский // Труды 4-го международного семинара по прикладной семиотике. — 2001. — С. 112-125.

87. Wang, X.-H. Leader-follower consensus for a class of nonlinear multi-agent systems / X.-H. Wang, H.-B. Ji // International Journal of Control, Automation and Systems. — 2012. — Vol. 10, № 1. — P. 27-35.

88. Kim, Y. A realistic decision making for task allocation in heterogeneous multiagent systems / Y. Kim, E. T. Matson // Procedia Computer Science. — 2016. — Vol. 94. — P. 487-494.

89. Лазарев, А. А. Теория расписаний. Задачи и алгоритмы / А. А. Лазарев, Е. Р. Гафаров. — М. : МГУ, 2011. — 320 с.

90. Jennings, N. R. A Roadmap of Agent Research and Development / N. R. Jennings, K. Sycara, M. Wooldridge // Autonomous Agents and Multi-Agent Systems. — 1998. — Vol. 1, № 1. — P. 7-38.

91.Leitao, P. Agent-based Distributed Manufacturing Control: A State-of-the-art Survey / P. Leitao // Engineering Applications of Artificial Intelligence. — 2009.

— Vol. 22, № 7. — P. 979-991.

92. Glover, F. Tabu Search / F. Glover, M. Laguna. — Berlin : Springer, 1997. — 385 p.

93.Dorigo, M. Ant Colony Optimization / M. Dorigo, M. Birattari, T. Stutzle // IEEE Computational Intelligence Magazine. — 2006. — Vol. 1, № 4. — P. 2839.

94.Potvin, J.-Y. Handbook of Metaheuristics / J.-Y. Potvin. — Berlin : Springer, 2010. — 560 p.

95.Brucker, P. Scheduling Algorithms / P. Brucker. — Berlin : Springer, 2007. — 371 p.

96.Lawler, E. L. Sequencing and Scheduling: Algorithms and Complexity / E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys // Handbooks in Operations Research and Management Science. — 1993. — Vol. 4. — P. 445522.

97.Garey, M. R. Computers and Intractability: A Guide to the Theory of NP-Completeness / M. R. Garey, D. S. Johnson. — San Francisco : Freeman, 1979.

— 338 p.

98. Smith, S. F. Constructing and Maintaining Detailed Production Plans: Investigations into the Development of Knowledge-Based Factory Scheduling Systems / S. F. Smith, M. S. Fox, P. S. Ow // AI Magazine. — 1988. — Vol. 9, № 4. — P. 45-57.

99. Van Laarhoven, P. J. M. Job Shop Scheduling by Simulated Annealing / P. J. M. Van Laarhoven, E. H. L. Aarts, J. K. Lenstra // Operations Research. — 1992.

— Vol. 40, № 1. — P. 113-125.

100. Feo, T. A. Greedy Randomized Adaptive Search Procedures / T. A. Feo, M. G. C. Resende // Journal of Global Optimization. — 1995. — Vol. 6. — P. 109-133.

101. Resende, M. G. C. Optimization by GRASP: Greedy Randomized Adaptive Search Procedures / M. G. C. Resende, C. C. Ribeiro. — Berlin : Springer, 2016. — 314 p.

102. Festa, P. An Annotated Bibliography of GRASP - Part I: Algorithms and Applications / P. Festa, M. G. C. Resende // Journal of Global Optimization. — 2009. — Vol. 43, № 2-3. — P. 209-235.

103. Grachev S.P. Методы и средства построения интеллектуальных систем для решения сложных задач адаптивного управления ресурсами в реальном времени // Automation and Remote Control. 2021. Т. 82. № 11. С. 1857-1885

104. Жиляев, А.А. Методы и средства построения «цифровых двойников» процессов управления предприятиями на основе онтологий и мультиагентных технологий: дис. ... канд. техн. наук: 05.13.01. - Самарский национальный исследовательский университет имени академика С. П. Королева, Самара, 2021-124 с.

105. Ларюхин, В.Б. Разработка методов и средств многоуровневого взаимодействия интеллектуальных систем управления ресурсами предприятий по созданию высокотехнологичных изделий: дис. ... канд. техн. наук: 05.13.01. - Самарский государственный технический университет, Самара, 2024-167 с.

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

систем", УБС, 39 (2012), 254-263

107. Иващенко, А.В., Мультиагентная система распределения производственных ресурсов в тяжелом машиностроении, ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ, 2010, 100-104 с.

108. Pechoucek, M. ExPlanTech: Multi-Agent Support for Manufacturing Production Planning / M. Pechoucek, A. Riha, V. Marik // International Journal of Production Research. - 2002. - Vol. 40, No. 15. - P. 3681-3692

109. Iglesias C.A. Methodology for the Development of Multiagent Systems / C.A. Iglesias, M. Garijo // Lecture Notes in AI. - 1999. - Vol. 1647. - P. 236-275.

110. Wooldridge M. The Gaia Methodology for Agent-Oriented Analysis and Design / M. Wooldridge, N. Jennings, D. Kinny // Autonomous Agents and Multi-Agent Systems. - 2000. - Vol. 3(3). - P. 285-312

111. Padgham L. Prometheus: A Methodology for Developing Intelligent Agents / L. Padgham, M. Winikoff // Proc. of AAMAS'02. - 2002. - P. 37-38

112. Genesereth, M.R. A Proposal for a DAI Testbed / M.R. Genesereth, S.P. Ketchpel, N.J. Nilsson // Distributed Artificial Intelligence / Eds. M.N. Huhns, M.P. Singh. - San Francisco : Morgan Kaufmann, 1987. - P. 119-129

113. Brooks, R.A. Intelligence Without Representation / R.A. Brooks // Artificial Intelligence. - 1991. - Vol. 47, No. 1-3. - P. 139-159

114. Cetnarowicz, K. M-agent architecture for decentralized resource allocation / K. Cetnarowicz, E. Nawarecki, M. Zabinska // Lecture Notes in Artificial Intelligence (LNAI). - 2002. - Vol. 2296. - P. 187-198

115. Ferguson, I. A. TouringMachines: An Architecture for Dynamic, Rational, Mobile Agents / I. A. Ferguson // PhD Dissertation. - University of Cambridge, 1992.- 211 p

116. Sutton, R.S. Dyna, an Integrated Architecture for Learning, Planning, and Reacting / R.S. Sutton // *Proceedings of the Seventh AAAI Conference on Artificial Intelligence (AAAI-91)*. - 1991. - P. 102-108

117. Dijkstra, E.W. A Note on Two Problems in Connexion with Graphs / E.W. Dijkstra // Numerische Mathematik. — 1959. — Vol. 1, № 1. — P. 269271

118. Bellman, R. On a Routing Problem / R. Bellman // Quarterly of Applied Mathematics. — 1958. — Vol. 16, № 1. — P. 87-90

119. Hart, P.E. A Formal Basis for the Heuristic Determination of Minimum Cost Paths / P.E. Hart, N.J. Nilsson, B. Raphael // IEEE Transactions on Systems Science and Cybernetics. — 1968. — Vol. 4, № 2. — P. 100-107

120. Floyd, R.W. Algorithm 97: Shortest Path / R.W. Floyd // Communications of the ACM. — 1962. — Vol. 5, № 6. — P. 345

121. Lee, C.Y. An Algorithm for Path Connections and Its Applications / C.Y.

Lee // IRE Transactions on Electronic Computers. — 1961. — Vol. EC-10, № 3. — P. 346-365

122. Moore, E.F. The Shortest Path Through a Maze / E.F. Moore

// Proceedings of the International Symposium on Switching Theory. — 1959. — P.285-292

123. Roy, B. ELECTRE III: Un algorithme de classement fondé sur une représentation floue des préférences / B. Roy, P. Bertier // Revue française d'automatique, d'informatique et de recherche opérationnelle. — 1971. — Vol. 5, № 3. — P. 3-24

Приложение А

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

(Справочное)

Описание:

Поиск осуществляется с применением метода BFS (Breadth-first search). Последовательно рассматриваются и оцениваются все технологически допустимые маршруты реализации конкретного заказа путем рекурсивного спуска. На выходе алгоритма отсортированный от лучшего к худшему весу массив routes. Сложность алгоритма - 0(2п) . Критерии оптимизации в функции оценки маршрута

определены со следующими весами: w1 = 0.3, w2 = 0.2, w3 = 0.1, где w1 -вес критерия стремления отдалить фактический срок реализации заказа от срока его сдачи, w2 - вес критерия стремления снижения стоимости реализации заказа путем уменьшения количества переналадочных операций, w3- вес критерия стремления гарантировать ограниченный уровень межоперационного пролеживания.

Метаданные: /// <summary>

/// Описание: найти отсортированные по весу маршруты заказа c учетом длины шкалы (горизонта планирования) /// </summary>

/// <param name="scale"> Шкала. Разбитая на минутки шкала, в рамках которой осуществляется построение расписания</param> /// <param name="order"> Заказ(деталь), расписание работ которого требуется построить</param>

/// <param name="next"> Указатель на номер операции, с которой требуется начинать поиск. При первом запуске равен 0</param> /// <param name="routes"> Массив, в который записываются найденные маршруты</param> /// <returns></returns>

void FindSortedOrderRoutes (Scale scale, Detail order, int next,

st<double,Scale> routes) {

for (int i = next; i < scale.Intervals.Count; i++) {

var interval = scale.Intervals[i];

var nextOperation = order.GetNextUnplannedOperation(); if (nextOperation == null) return;

if (interval.IsFree()) {

interval.AssignToOperation(nextOperation); nextOperation.MarkPartlyPlannedQ;

if (nextOperation.Planned) {

if (order.OrderIsPlanned()) {

var scaleToSave = new Scale(scale.Intervals.Count); scale.CopyTo(scaleToSave);

var weight = OrderAlgos.GetWeightedRoute(scaleToSave); routes.Add(weight, scaleToSave);

scale.Intervals[i] = new ScaleInteval(interval.Index); _nextOperation.PlannedDuration = 0;_

scale.Intervals[i] = new ScaleInteval(interval.Index); FindSortedOrderRoutes(scale, order, i + 1, routes); return;

FindSortedOrderRoutes(scale, order, i + 1, routes);

if (scale.Intervals[i].PlannedOperation.Duration > 1) {

if (scale.Intervals[i].PlannedOperation.PlannedDuration != 0) {

var rightBorder = i; var leftBorder = i -ntervals[i].PlannedOperation.Duration+1;

for (int j = rightBorder; j >= leftBorder; j--) {

scale.Intervals[j].PlannedOperation.UnMarkPartlyPlanned();

scale.Intervals[j] = new ScaleInteval(interval.Index); }

}

}

else {

scale.Intervals[i] = new ScaleInteval(interval.Index); nextOperation.PlannedDuration = 0;

}

}

else {

FindSortedOrderRoutes(scale, order, i + 1, routes); scale.Intervals[i] = new ScaleInteval(interval.Index); nextOperation.PlannedDuration = 0;

}

}

scale.Intervals[i] = new ScaleInteval(interval.Index); nextOperation.PlannedDuration = 0;

}

}

Используемые сущности:

Scale - временная шкала, на которой осуществляется планирование(минутки)

/// <summary>

/// Шкала временных интервалов, используемых для планирования /// </summary>

public class Scale {

public List<ScaleInteval> Intervals;

public Scale(int lenght) {

Intervals = new List<ScaleInteval>();

for (var i = 1; i <= lenght; i++) {

Intervals.Add(new ScaleInteval(i));

}

}

/// <summary>

/// Клонировать шкалу в другой экземпляр /// </summary>

/// <param name="newScale"></param> _public void CopyTo(Scale newScale)_

for (var index = 0; index < Intervals.Count; index++) {

var interval = Intervals[index];

var newScaledInterval = new ScaleInteval(index) {Index = interval.Index};

if (interval.PlannedOperation == null) {

newScaledInterval.PlannedOperation = null;

}

else {

newScaledInterval.PlannedOperation = new Operation(interval.PlannedOperation.OrderId,

interval.PlannedOperation.TechNumber, interval.PlannedOperation.OperationType,

interval.PlannedOperation.Duration, interval.PlannedOperation.Cost);

}

newScale.Intervals[index] = newScaledInterval;

}

}

}

ScaleInterval - один интервал временной шкалы Scale

/// <summary>

/// Один интервал шкалы

/// </summary>

public class ScaleInteval {

/// <summary> /// Заблокирован /// </summary> public bool Locked;

/// <summary> /// Номер /// </summary>

public int Index { get; set; } /// <summary>

/// Запланированная операция /// </summary>

public Operation PlannedOperation { get; set; }

/// <summary>

/// Один интервал шкалы

/// </summary>

/// <param name="index">Номер</param>

public ScaleInteval(int index) {

Index = index;

}

/// <summary>

/// Закрепить интервал за операцией /// </summary>

/// <param name="operation"></param>

public void AssignToOperation(Operation operation) {

PlannedOperation = operation;

}

/// <summary>

/// Интвервал свободен?

III </summary>

III <returns><|returns>

public bool IsFree() {

return PlannedOperation ==null;

}

III <summary>

III Текстовое представление

III <Isummary>

III <returns><Ireturns>

public override string ToString() {

return $"Index = {Index} Oparation = {PlannedOperation}";

}

}

Detail - деталь (заказ), которую требуется изготовить

/// <summary> /// Деталь /// </summary>

public class Detail {

/// <summary> /// Номер заказа /// </summary>

public string Orderld { get; private set; }

/// <summary> /// Наименование /// </summary>

public string Name { get; private set; } /// <summary>

/// Набор операцией к выполнению /// </summary>

public List<Operation> Operations;

/// <summary> /// Деталь /// </summary>

public Detail(string orderld, string name, List<Operation> operations) {

Orderld = orderld; Name = name;

Operations = operations;

}

/// <summary>

/// Заказ запланирован?

/// </summary>

/// <returns></returns>

public bool OrderIsPlanned() {

foreach (var operation in Operations) {

if (!operation.Planned) return false;

}

return true;

_}_

/// <summary>

/// Получить следующую по порядку незапланированную операцию

/// </summary>

/// <returns></returns>

public Operation GetNextUnplannedOperation() {

foreach (var operation in Operations) {

if (!operation.Planned) return operation;

}

return null;

}

}

Operation - технологическая операция, часть технологического процесса

/// <summary>

/// Технологическая операция /// </summary>

public class Operation {

/// <summary> /// Запланирована? /// </summary>

public bool Planned => PlannedDuration == Duration;

/// <summary> /// Номер заказа /// </summary>

public string OrderId { get; private set; } /// <summary>

/// Порядковый номер операции /// </summary>

public int TechNumber { get; private set; }

/// <summary> /// Вид операции /// </summary>

public OperationType OperationType { get; private set; } /// <summary>

/// Длительность операции, мин /// </summary>

public int Duration { get; private set; }

/// <summary>

/// Стоимость операции

/// </summary>

public int Cost { get; private set; } /// <summary>

/// Уже запланированная длительность /// </summary>

public int PlannedDuration = 0; /// <summary>

/// Технологическая операция _/// </summary>_

public Operation(string orderld, int techNumber, OperationType type, int duration,

int cost) {

Orderld = orderld; TechNumber = techNumber; OperationType = type; Duration = duration; Cost = cost;

}

/// <summary>

/// Пометить частично запланированной (+ 1 мин.) /// </summary>

public void MarkPartlyPlanned() {

PlannedDuration++;

}

/// <summary>

/// Уменьшить на 1 мин запланированную длительность /// </summary>

public void UnMarkPartlyPlanned() {

PlannedDuration--;

}

/// <summary>

/// Текстовое представление

/// </summary>

/// <returns></returns>

public override string ToString() {

return $"{OrderId} {OperationType} {Duration}";

}

}

Resource- ресурс, на котором выполняются технологические операции

/// <summary> /// Ресурс(станок) /// </summary>

public class Resource {

/// <summary> /// Имя ресурса /// </summary>

public string Name { get; private set; } /// <summary>

/// Операции, которые может выполнять ресурс /// </summary>

public List<OperationType> PerfomingOperations;

/// <summary>

/// Список переналадок

/// </summary>

public List<ChangeOver> ChangeOvers;

/// <summary> /// Ресурс(станок) /// </summary>

public Resource(string name, List<OperationType> perfomingOperations,List<ChangeOver> changeOvers)

Name = name;

PerfomingOperations = perfomingOperations; ChangeOvers = changeOvers;

}

}

ChangeOver -описание переналадки между двумя операциями

/// <summary>

/// Переналадка /// </summary>

public class ChangeOver {

/// <summary> /// Операция 1 /// </summary>

public OperationType Operation1;

/// <summary> /// Операция 2 /// </summary>

public OperationType Operation2;

/// <summary> /// Стоимость /// </summary> public int Cost;

/// <summary> /// Переналадка /// </summary>

public ChangeOver(OperationType operation1,OperationType operation2,int cost) {

Operation1 = operation1; Operation2 = operation2; Cost = cost;

}

}

GetWeightedRoutes -алгоритм взвешивания маршрутов в соответствии с определенными критериями

/// <summary>

/// Получить взвешенные маршруты /// </summary>

/// <param name="allRoutes"></param> /// <param name="order"></param> /// <returns></returns>

public static List<Tuple<Route, double>> GetWeightedRoutes (List<Route> allRoutes,

Order order) {

var weiths = new List<double>();

var result = new List<Tuple<Route, double>>();

foreach (var route in allRoutes) {

//Чем дешевле и дальше от срока сдачи заказа, тем вес больше double w = 0;

var m = (double)order.Money;

var c = GetRouteExecutionCost(route);

var p = GetRouteExecutionPenalty(route);

if (c > m) {

weiths.Add(w); continue;

}

var potentialEnd = route.Stages.Last().Capability.End;

var fullduration = (order.DueDate - Time.Now()).TotalMinutes;

var remainingduration = (order.DueDate - potentialEnd).TotalMinutes;

//Параметр, от 0 до 1. Если 0 - наступил срок сдачи, если 1 - мы максимально далеко от срока сдачи

var remain = remainingduration / fullduration;

//Дельта (ризница между сроком сдачи и потенциальным завершением маршрута) var delta = GetR(order,route, order.DueDate); //Растяжимость маршрута var extens = GetE2(route);

double w = (delta + Math.Sqrt(extens * remain)) * m / c * (1 / p); weiths.Add(w);

result.Add(Tuple.Create(route, w));

}

result.Sort((a, b) => b.Item2.CompareTo(a.Item2)); return result;

}

GetE -алгоритм, вычисляющий коэффициент растянутости(коэффициент межоперационного пролеживания) технологического маршрута

/// <summary>

/// Получить коэффициент растянутости маршрута /// </summary>

/// <param name="route"></param> /// <returns></returns>

private static double GetE(Route route) {