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

Генетические алгоритмы, предложенные в начале 70-х годов, являются одним из самых распространённых вариантов реализации эволюционных алгоритмов. Генетические алгоритмы используют аналогию между естественным отбором и процессом выбора наилучшего решения из множества возможных. Носителями решений являются особи, в "хромосомах" которых закодированы те или иные существенные параметры. Ключевой момент здесь - возможность задать функции оценки приспособленности особей (fitness function), ответственной за "половой отбор" (эволюционная аналогия задачи оптимизации: наиболее привлекательная самка выбирает самого статусного самца).

Схема работы генетических алгоритмов выглядит следующим образом.

1. Задается способ кодирования параметров задачи в "хромосомах".
2. Создается исходная популяция (начальное решение).
3. Рассчитывается функция приспособленности каждой особи.
4. Для наиболее приспособленных особей производится "скрещивание" и рождение новых особей, содержащих признаки обоих родителей. При этом передача признаков осуществляется в соответствии с одним из выбранных способов "обмена участков хромосом". Наименее приспособленные особи "отмирают" и заменяются новорожденными.
5. Осуществляется мутация некоторой части особей добавлением в процесс поиска элемента случайности.
6. Шаги 2-5 итерационно повторяются заданное число раз.
7. Из оставшейся популяции выбираются лучшие особи, "хромосомы" декодируются, а получаемое таким образом решение соответствует локальному оптимуму.

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

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

Метод роящихся частиц (particle swarm). Это наиболее простой и, что удивительно, один из самых молодых методов эволюционного программирования, появившийся в середине 90-х годов. Группа исследователей, занимавшихся этологией птиц и рыб, их социальной организацией, пришла к выводу о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру "притяжения", постепенно замедляя скорость полёта.

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

Схема работы алгоритма выглядит следующим образом

1. Создаётся исходная "случайная" популяция частиц.
2. Для каждой частицы рассчитывается целевая функция.
3. Лучшая частица с точки зрения целевой функции объявляется "центром притяжения".
4. Векторы скоростей всех частиц устремляются к этому "центру", при этом чем дальше частица находится от него, тем большим ускорением она обладает.
5. Осуществляется расчёт новых координат частиц в пространстве решений.
6. Шаги 2-5 повторяются заданное число раз.
7. Последний "центр тяжести" объявляется найденным оптимальным решением.

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

Табуированный поиск (Tabu Search). Данная процедура представляет собой вариацию известного метода градиентного спуска с памятью. В процессе поиска ведётся список табуированных (запрещённых для перехода) позиций (из числа уже посещённых и рассчитанных). Критические параметры алгоритма - глубина списка за претов, определение текущего состояния, размер области вокруг текущего состояния. В процессе поиска осуществляются операции аспирации (включение в запрещённый список состояний вокруг текущего состояния) и диверсификации, которая добавляет фактор случайности в процесс поиска.

Моделирование отжига (Simulated Annealing). Метод, разработанный в 80-х годах, основан на аналогии с физическим процессом охлаждения металла и переходом его в состояние с минимальной энергией кристаллической решётки. Изначально он использовался для моделирования поведения системы атомов при разных температурах, но впоследствии был расширен для решения комбинаторных задач.

Схема применения метода достаточно проста.

1. Задается начальное условие.
2. Выбираются соседние состояния и определяется вероятность перехода в каждое из этих состояний, которая зависит от их "энергии".
3. Уменьшается температура (от нее зависит вероятность перехода в новое состояние).
4. Шаги 2-3 повторяются заданное число раз.

Планирование на современном предприятии

Программные продукты, реализующие вышеописанные алгоритмы оптимизации для составления детальных производственных расписаний, относятся к классу APS-систем (Advanced Planning & Scheduling). Это относительно молодое направление корпоративных информационных систем, возникшее в конце 80-х годов и снискавшее среди менеджеров по логистике и планированию западных предприятий заслуженное уважение. Большинство APS-систем являются инструментами имитационного моделирования производственной деятельности и применяются для поддержки принятия решений в области операционного менеджмента промышленных предприятий.

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

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

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

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

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

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

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

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

Анализ основной деятельности предприятия предполагает использование простых и ёмких ключевых показателей эффективности (КПЭ) для диагностики ситуации на предприятии. Современные APS-системы позволяют оценить множество обобщённых и отраслевых ключевых показателей такого рода по имеющемуся производственному расписанию. Данный инструмент предназначен в первую очередь для топ-менеджеров, руководителей технологических подразделений и планово-диспетчерских служб.

Что важно знать специалисту, выбирающему систему оперативного планирования?

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

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

1. На ограничения, связанные со специфическими типами оборудования: печами, танками, конвейерами, рольгангами, трубопроводами, соединяющими отдельные единицы парка машин. Важна возможность моделирования минимальной и максимальной ёмкости загрузки оборудования, процессов заполнения и освобождения содержимого танков.
2. На те, что имеют отношение к технологическим маршрутам и спецификациям изделий. Можно ли задавать произвольную последовательность прохождения операций в маршруте, параллельное их выполнение, жёсткую стыковку типа "начало - конец", ограничивать максимальное время жизни отдельных переделов? Немаловажной является возможность описания и реализации альтернативных производственных маршрутов, задания длительностей отдельных операции в зависимости от требуемого для их выполнения оборудования, указания приоритетов использования этого оборудования. Для сборочных и рецептурных производств существенно и то, каким способом можно описать спецификацию/рецепт изделия: какова максимальная глубина вложенности компонентов, можно ли точно указывать временной отрезок потребления сырья и материалов в рамках технологического маршрута?
3. Допускается ли планирование с учётом прогнозируемых поставок сырья и материалов, ограниченного числа операторов в отдельные смены, наличия доступной технологической оснастки и инструмента?
4. Можно ли учитывать динамические ограничения, связанные с поломками оборудования, невыходом сотрудников на работу, изменением скорости работы машин уже в процессе реализации плана?
5. Допускается ли планирование взаимозаменяемых компонентов (полуфабрикатов) не для каждого производственного заказа в отдельности, а более крупными партиями, как это делается при использовании алгоритмов MRP-II в ERPсистемах?

Во-вторых, немаловажный фактор - скорость работы системы. Как правило, скорость расчёта/перерасчёта оперативного производственного расписания должна составлять минуты, максимум десятки минут. В связи с тем что в большинстве APS-систем сначала информационная модель загружается в память, их производительность определяется реализованными алгоритмами и мало зависит от выбора СУБД.

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

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

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

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

Большинство APS-продуктов способны работать в информационной инфраструктуре предприятия автономно. Тем не менее многие данные, которые используются в процессе расчёта, могут быть получены из внешних систем: портфель заказов, график закупки сырья и справочник оборудования - из ERP, технологическая информация и спецификации изделий - из PDM/PLM (Product Data Management), сведения о ходе производственного процесса - из MES (Manufacturing Execution System), данные по складским остаткам - из WMS (Warehouse Management System), графики планово-предупредительных ремонтов - из EAM (Enterprise Asset Management). Приложения APS также выдают весьма важную для управления предприятием информацию. Это и производственные расписания, экономический анализ которых можно провести в ERP-системах, и очереди заказов для выполнения на машинах, управляемых MES-системами, интегрированными с АСУ ТП, и наряды на работы для LIMSрешений (Labor Information Management System). Беспрепятственная передача указанных потоков данных невозможна без применения современных средств интеграции приложений EAI (Enterprise Application Integration). Некоторые APSсистемы имеют в своем составе подобные инструменты.

С чего начать?

Прежде чем приступить к выбору системы планирования следует чётко представлять себе, какие результаты необходимо достичь с ее помощью. Чаще всего на отечественных предприятиях обращают внимание на коэффициент загрузки оборудования, повысить который стремятся всеми возможными способами. Является ли этот индикатор основным на пути улучшения производственной деятельности? Как показывает практика зарубежных предприятий, показатель загрузки оборудования конечно же важен, но не критичен при анализе конкурентных преимуществ предприятия: можно успешно перерабатывать сырьё, переводя его в отходы, загружая оборудование на 95%.

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

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

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

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

Насколько нам известно, подобная функция, которую можно было бы назвать "оптимизатором оптимизатора", сегодня реализована только в продукте компании ORTEMS S.A.S (www.ortems.com). Для заданных высшим руководством предприятия целей и показателей эффективности она позволяет сформулировать такие составные правила разрешения конфликтов планирования, которые обеспечат достижение поставленных целей вне зависимости от меняющихся внешних условий (т. е. находит глобально оптимизированный план).

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

Шаги в будущее

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